Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs

• URL: http://arxiv.org/abs/1804.11242v5
• Date: Tue, 19 Sep 2023 17:44:44 GMT
• Title: Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs
• Authors: Paul Rosen, Mustafa Hajij, Bei Wang
• Abstract summary: We propose to apply the mapper construction -- a popular tool in topological data analysis -- to graph visualization. We develop a variation of the mapper construction targeting weighted, undirected graphs, called mog, which generates homology-preserving skeletons of graphs. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.
• Score: 5.86893539706548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Node-link diagrams are a popular method for representing graphs that capture relationships between individuals, businesses, proteins, and telecommunication endpoints. However, node-link diagrams may fail to convey insights regarding graph structures, even for moderately sized data of a few hundred nodes, due to visual clutter. We propose to apply the mapper construction -- a popular tool in topological data analysis -- to graph visualization, which provides a strong theoretical basis for summarizing the data while preserving their core structures. We develop a variation of the mapper construction targeting weighted, undirected graphs, called {\mog}, which generates homology-preserving skeletons of graphs. We further show how the adjustment of a single parameter enables multi-scale skeletonization of the input graph. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.

Related papers

• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53:52Z)
• SynGraphy: Succinct Summarisation of Large Networks via Small Synthetic Representative Graphs [4.550112751061436]
  We describe SynGraphy, a method for visually summarising the structure of large network datasets. It works by drawing smaller graphs generated to have similar structural properties to the input graphs.
  arXiv  Detail & Related papers  (2023-02-15T16:00:15Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Joint Network Topology Inference via a Shared Graphon Model [24.077455621015552]
  We consider the problem of estimating the topology of multiple networks from nodal observations. We adopt a graphon as our random graph model, which is a nonparametric model from which graphs of potentially different sizes can be drawn.
  arXiv  Detail & Related papers  (2022-09-17T02:38:58Z)
• 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)
• SHGNN: Structure-Aware Heterogeneous Graph Neural Network [77.78459918119536]
  This paper proposes a novel Structure-Aware Heterogeneous Graph Neural Network (SHGNN) to address the above limitations. We first utilize a feature propagation module to capture the local structure information of intermediate nodes in the meta-path. Next, we use a tree-attention aggregator to incorporate the graph structure information into the aggregation module on the meta-path. Finally, we leverage a meta-path aggregator to fuse the information aggregated from different meta-paths.
  arXiv  Detail & Related papers  (2021-12-12T14:18:18Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• 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)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• 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.