A pseudo-inverse of a line graph

• URL: http://arxiv.org/abs/2508.09412v2
• Date: Thu, 09 Oct 2025 08:59:58 GMT
• Title: A pseudo-inverse of a line graph
• Authors: Sevvandi Kandanaarachchi, Philip Kilby, Cheng Soon Ong,
• Abstract summary: We investigate the case when there is a small perturbation in the space of line graphs, and try to recover the corresponding root graph.<n>We propose a linear integer program that edits the smallest number of edges in the line graph, that allow a root graph to be found.
• Score: 7.365028217363608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Line graphs are an alternative representation of graphs where each vertex of the original (root) graph becomes an edge. However not all graphs have a corresponding root graph, hence the transformation from graphs to line graphs is not invertible. We investigate the case when there is a small perturbation in the space of line graphs, and try to recover the corresponding root graph, essentially defining the inverse of the line graph operation. We propose a linear integer program that edits the smallest number of edges in the line graph, that allow a root graph to be found. We use the spectral norm to theoretically prove that such a pseudo-inverse operation is well behaved. Illustrative empirical experiments on Erd\H{o}s-R\'enyi graphs show that our theoretical results work in practice.

Related papers

• Theoretical Insights into Line Graph Transformation on Graph Learning [3.0574700762497744]
  Line graph transformation has been widely studied in graph theory, where each node in a line graph corresponds to an edge in the original graph.<n>This has inspired a series of graph neural networks (GNNs) applied to transformed line graphs, which have proven effective in various graph representation learning tasks.<n>In this study, we focus on two types of graphs known to be challenging to the Weisfeiler-Leman (WL) tests: Cai-F"urer-Immerman (CFI) graphs and strongly regular graphs.
  arXiv  Detail & Related papers  (2024-10-21T16:04:50Z)
• Graphons of Line Graphs [6.822247359790484]
  We show a simple method that can shed light on a subset of sparse graphs.<n>We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs.<n>In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs.
  arXiv  Detail & Related papers  (2024-09-03T06:50:03Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words. A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
  arXiv  Detail & Related papers  (2024-02-04T12:29:40Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  We propose fine-grained graph rationalization (FIG) for graph machine learning.<n>Our idea is driven by the self-attention mechanism, which provides rich interactions between input nodes.<n>Our experiments involve 7 real-world datasets, and the proposed FIG shows significant performance advantages compared to 13 baseline methods.
  arXiv  Detail & Related papers  (2023-12-13T02:56:26Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• A Graph Convolution for Signed Directed Graphs [0.0]
  Graph convolutions for signed directed graphs have not been delivered much yet. We propose a novel complex Hermitian adjacency matrix that encodes graph information via complex numbers. To the best of our knowledge, it is the first spectral convolution for graphs with signs.
  arXiv  Detail & Related papers  (2022-08-23T01:58:35Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  We present an extensive survey of various exact and inexact graph matching techniques. A category of graph matching algorithms is presented, which reduces the graph size by removing the less important nodes. We introduce a novel approach to measure graph similarity using geometric graphs.
  arXiv  Detail & Related papers  (2020-12-30T18:51:06Z)
• 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.