Balancing between the Local and Global Structures (LGS) in Graph Embedding

• URL: http://arxiv.org/abs/2308.16403v2
• Date: Sat, 2 Sep 2023 00:11:42 GMT
• Title: Balancing between the Local and Global Structures (LGS) in Graph Embedding
• Authors: Jacob Miller and Vahan Huroyan and Stephen Kobourov
• Abstract summary: We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. We evaluate the performance of LGS with synthetic and real-world datasets and our results indicate that it is competitive with the state-of-the-art methods.
• Score: 1.4732811715354455
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. Some embedding methods aim to capture global structures, while others attempt to preserve local neighborhoods. Few methods attempt to do both, and it is not always possible to capture well both local and global information in two dimensions, which is where most graph drawing live. The choice of using a local or a global embedding for visualization depends not only on the task but also on the structure of the underlying data, which may not be known in advance. For a given graph, LGS aims to find a good balance between the local and global structure to preserve. We evaluate the performance of LGS with synthetic and real-world datasets and our results indicate that it is competitive with the state-of-the-art methods, using established quality metrics such as stress and neighborhood preservation. We introduce a novel quality metric, cluster distance preservation, to assess intermediate structure capture. All source-code, datasets, experiments and analysis are available online.

Related papers

• Efficient Multi-View Graph Clustering with Local and Global Structure Preservation [59.49018175496533]
  We propose a novel anchor-based multi-view graph clustering framework termed Efficient Multi-View Graph Clustering with Local and Global Structure Preservation (EMVGC-LG) Specifically, EMVGC-LG jointly optimize anchor construction and graph learning to enhance the clustering quality. In addition, EMVGC-LG inherits the linear complexity of existing AMVGC methods respecting the sample number.
  arXiv  Detail & Related papers  (2023-08-31T12:12:30Z)
• Local2Global: A distributed approach for scaling representation learning on graphs [10.254620252788776]
  We propose a decentralised "local2global"' approach to graph representation learning, that one can a-priori use to scale any embedding technique. We show that our approach achieves a good trade-off between scale and accuracy on edge reconstruction and semi-supervised classification. We also consider the downstream task of anomaly detection and show how one can use local2global to highlight anomalies in cybersecurity networks.
  arXiv  Detail & Related papers  (2022-01-12T23:00:22Z)
• An Entropy-guided Reinforced Partial Convolutional Network for Zero-Shot Learning [77.72330187258498]
  We propose a novel Entropy-guided Reinforced Partial Convolutional Network (ERPCNet) ERPCNet extracts and aggregates localities based on semantic relevance and visual correlations without human-annotated regions. It not only discovers global-cooperative localities dynamically but also converges faster for policy gradient optimization.
  arXiv  Detail & Related papers  (2021-11-03T11:13:13Z)
• Tackling the Local Bias in Federated Graph Learning [48.887310972708036]
  In Federated graph learning (FGL), a global graph is distributed across different clients, where each client holds a subgraph. Existing FGL methods fail to effectively utilize cross-client edges, losing structural information during the training. We propose a novel FGL framework to make the local models similar to the model trained in a centralized setting.
  arXiv  Detail & Related papers  (2021-10-22T08:22:36Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)
• Local2Global: Scaling global representation learning on graphs via local training [6.292766967410996]
  We propose a decentralised "local2global" approach to graph representation learning. We train local representations for each patch independently and combine the local representations into a globally consistent representation. Preliminary results on medium-scale data sets are promising, with a graph reconstruction performance for local2global that is comparable to that of globally trained embeddings.
  arXiv  Detail & Related papers  (2021-07-26T14:08:31Z)
• Self-supervised Graph-level Representation Learning with Local and Global Structure [71.45196938842608]
  We propose a unified framework called Local-instance and Global-semantic Learning (GraphLoG) for self-supervised whole-graph representation learning. Besides preserving the local similarities, GraphLoG introduces the hierarchical prototypes to capture the global semantic clusters. An efficient online expectation-maximization (EM) algorithm is further developed for learning the model.
  arXiv  Detail & Related papers  (2021-06-08T05:25:38Z)
• LGD-GCN: Local and Global Disentangled Graph Convolutional Networks [35.71362724342354]
  Disentangled Graph Convolutional Network (DisenGCN) is an encouraging framework to disentangle the latent factors arising in a real-world graph. We introduce a novel Global Disentangled Graph Convolutional Network (LGD-GCN) to capture both local and global information for graph disentanglement.
  arXiv  Detail & Related papers  (2021-04-24T06:40:35Z)
• Multi-Level Graph Convolutional Network with Automatic Graph Learning for Hyperspectral Image Classification [63.56018768401328]
  We propose a Multi-level Graph Convolutional Network (GCN) with Automatic Graph Learning method (MGCN-AGL) for HSI classification. By employing attention mechanism to characterize the importance among spatially neighboring regions, the most relevant information can be adaptively incorporated to make decisions. Our MGCN-AGL encodes the long range dependencies among image regions based on the expressive representations that have been produced at local level.
  arXiv  Detail & Related papers  (2020-09-19T09:26:20Z)
• Deep graph learning for semi-supervised classification [11.260083018676548]
  Graph learning (GL) can dynamically capture the distribution structure (graph structure) of data based on graph convolutional networks (GCN) Existing methods mostly combine the computational layer and the related losses into GCN for exploring the global graph or local graph. Deep graph learning(DGL) is proposed to find the better graph representation for semi-supervised classification.
  arXiv  Detail & Related papers  (2020-05-29T05:59:45Z)

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.