Efficient Network Embedding by Approximate Equitable Partitions

• URL: http://arxiv.org/abs/2409.10160v1
• Date: Mon, 16 Sep 2024 10:51:24 GMT
• Title: Efficient Network Embedding by Approximate Equitable Partitions
• Authors: Giuseppe Squillace, Mirco Tribastone, Max Tschaikowski, Andrea Vandin,
• Abstract summary: We introduce a simple and efficient embedding technique based on approximate variants of equitable partitions. We exploit a relationship between equitable partitions and equivalence relations for Markov chains and ordinary differential equations to develop a partition refinement algorithm. We report comparable -- when not superior -- performance for visualization, classification, and regression tasks at a cost between one and three orders of magnitude smaller.
• Score: 0.15978270011184256
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structural network embedding is a crucial step in enabling effective downstream tasks for complex systems that aims to project a network into a lower-dimensional space while preserving similarities among nodes. We introduce a simple and efficient embedding technique based on approximate variants of equitable partitions. The approximation consists in introducing a user-tunable tolerance parameter relaxing the otherwise strict condition for exact equitable partitions that can be hardly found in real-world networks. We exploit a relationship between equitable partitions and equivalence relations for Markov chains and ordinary differential equations to develop a partition refinement algorithm for computing an approximate equitable partition in polynomial time. We compare our method against state-of-the-art embedding techniques on benchmark networks. We report comparable -- when not superior -- performance for visualization, classification, and regression tasks at a cost between one and three orders of magnitude smaller using a prototype implementation, enabling the embedding of large-scale networks which could not be efficiently handled by most of the competing techniques.

Related papers

• Detecting and Approximating Redundant Computational Blocks in Neural Networks [25.436785396394804]
  intra-network similarities present new opportunities for designing more efficient neural networks. We introduce a simple metric, Block Redundancy, to detect redundant blocks, and propose Redundant Blocks Approximation (RBA) to approximate redundant blocks. RBA reduces model parameters and time complexity while maintaining good performance.
  arXiv  Detail & Related papers  (2024-10-07T11:35:24Z)
• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Unifying Feature and Cost Aggregation with Transformers for Semantic and Visual Correspondence [51.54175067684008]
  This paper introduces a Transformer-based integrative feature and cost aggregation network designed for dense matching tasks. We first show that feature aggregation and cost aggregation exhibit distinct characteristics and reveal the potential for substantial benefits stemming from the judicious use of both aggregation processes. Our framework is evaluated on standard benchmarks for semantic matching, and also applied to geometric matching, where we show that our approach achieves significant improvements compared to existing methods.
  arXiv  Detail & Related papers  (2024-03-17T07:02:55Z)
• Generalized Correspondence Matching via Flexible Hierarchical Refinement and Patch Descriptor Distillation [13.802788788420175]
  Correspondence matching plays a crucial role in numerous robotics applications. This paper addresses the limitations of deep feature matching (DFM), a state-of-the-art (SoTA) plug-and-play correspondence matching approach. Our proposed method achieves an overall performance in terms of mean matching accuracy of 0.68, 0.92, and 0.95 with respect to the tolerances of 1, 3, and 5 pixels, respectively.
  arXiv  Detail & Related papers  (2024-03-08T15:32:18Z)
• Label-efficient Segmentation via Affinity Propagation [27.016747627689288]
  Weakly-supervised segmentation with label-efficient sparse annotations has attracted increasing research attention to reduce the cost of laborious pixel-wise labeling process. We formulate the affinity modeling as an affinity propagation process, and propose a local and a global pairwise affinity terms to generate accurate soft pseudo labels. An efficient algorithm is also developed to reduce significantly the computational cost.
  arXiv  Detail & Related papers  (2023-10-16T15:54:09Z)
• Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
  Domain-adaptive hash learning has enjoyed considerable success in the computer vision community. We develop an unsupervised domain-adaptive hash learning method for networks, dubbed UDAH.
  arXiv  Detail & Related papers  (2021-08-20T12:09:38Z)
• Manifold Regularized Dynamic Network Pruning [102.24146031250034]
  This paper proposes a new paradigm that dynamically removes redundant filters by embedding the manifold information of all instances into the space of pruned networks. The effectiveness of the proposed method is verified on several benchmarks, which shows better performance in terms of both accuracy and computational cost.
  arXiv  Detail & Related papers  (2021-03-10T03:59:03Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  We train a graph convolutional network to fit the performance of sampled sub-networks. With this strategy, we achieve a higher rank correlation coefficient in the selected set of candidates.
  arXiv  Detail & Related papers  (2020-04-17T19:12:39Z)
• Weakly-Supervised Semantic Segmentation by Iterative Affinity Learning [86.45526827323954]
  Weakly-supervised semantic segmentation is a challenging task as no pixel-wise label information is provided for training. We propose an iterative algorithm to learn such pairwise relations. We show that the proposed algorithm performs favorably against the state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-19T10:32:03Z)

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.