Fused Partial Gromov-Wasserstein for Structured Objects

• URL: http://arxiv.org/abs/2502.09934v2
• Date: Fri, 26 Sep 2025 17:17:32 GMT
• Title: Fused Partial Gromov-Wasserstein for Structured Objects
• Abstract summary: We propose the Fused Partial Gromov-Wasserstein (FPGW) framework, which extends FGW to accommodate unbalanced data.<n>In this work, we establish the relationship between FPGW and FGW and prove the metric properties of FPGW.<n>We evaluate the FPGW distance through graph matching, graph classification and graph clustering experiments, demonstrating its robust performance.
• Score: 20.979925870718233
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structured data, such as graphs, is vital in machine learning due to its capacity to capture complex relationships and interactions. In recent years, the Fused Gromov-Wasserstein (FGW) distance has attracted growing interest because it enables the comparison of structured data by jointly accounting for feature similarity and geometric structure. However, as a variant of optimal transport (OT), classical FGW assumes an equal mass constraint on the compared data. In this work, we relax this mass constraint and propose the Fused Partial Gromov-Wasserstein (FPGW) framework, which extends FGW to accommodate unbalanced data. Theoretically, we establish the relationship between FPGW and FGW and prove the metric properties of FPGW. Numerically, we introduce Frank-Wolfe solvers and Sinkhorn solvers for the proposed FPGW framework. Finally, we evaluate the FPGW distance through graph matching, graph classification and graph clustering experiments, demonstrating its robust performance.

Related papers

• When Do Graph Foundation Models Transfer? A Data-Centric Theory [68.54337055801571]
  Graph foundation models (GFMs) aim to reuse a single backbone across diverse graph domains, yet their transfer is often uneven and can exhibit negative transfer.<n>We show that for both set-based and message-passing tokenizations, any Lipschitz backbone admits an explicit decomposition of cross-domain output shift.<n>A key ingredient is positional-encoding (PE) stability: we establish stability guarantees for spectral PEs and highlight contrasting behaviors of eigenvector- versus subspace-based PEs.
  arXiv  Detail & Related papers  (2026-05-28T12:07:27Z)
• Fused Gromov-Wasserstein Distance with Feature Selection [10.486119449960851]
  Fused Gromov-Wasserstein (FGW) distances provide a principled framework for comparing objects by jointly aligning structure and node features.<n>We introduce FGW distances with feature selection, which incorporate adaptive feature suppression weights into the FGW objective.<n>Experiments illustrate how feature suppression enhances interpretability and reveals task-relevant structure, with a special application to computational redistricting.
  arXiv  Detail & Related papers  (2026-05-12T14:11:25Z)
• Breaking the Reasoning Horizon in Entity Alignment Foundation Models [22.785226234096882]
  Existing EA models lack transferability and are incapable of aligning unseen KGs without retraining.<n>We propose a EA foundation model driven by a parallel encoding strategy.<n>We utilize seed EA pairs as local anchors to guide the information flow, initializing and encoding two parallel streams simultaneously.
  arXiv  Detail & Related papers  (2026-01-29T02:18:45Z)
• Partitioning Message Passing for Graph Fraud Detection [57.928658584067556]
  Label imbalance and homophily-heterophily mixture are the fundamental problems encountered when applying Graph Neural Networks (GNNs) to Graph Fraud Detection (GFD) tasks.<n>Existing GNN-based GFD models are designed to augment graph structure to accommodate the inductive bias of GNNs towards homophily.<n>In our work, we argue that the key to applying GNNs for GFD is not to exclude but to em distinguish neighbors with different labels.
  arXiv  Detail & Related papers  (2024-11-16T11:30:53Z)
• Chasing Fairness in Graphs: A GNN Architecture Perspective [73.43111851492593]
  We propose textsfFair textsfMessage textsfPassing (FMP) designed within a unified optimization framework for graph neural networks (GNNs) In FMP, the aggregation is first adopted to utilize neighbors' information and then the bias mitigation step explicitly pushes demographic group node presentation centers together. Experiments on node classification tasks demonstrate that the proposed FMP outperforms several baselines in terms of fairness and accuracy on three real-world datasets.
  arXiv  Detail & Related papers  (2023-12-19T18:00:15Z)
• Fake It Till Make It: Federated Learning with Consensus-Oriented Generation [52.82176415223988]
  We propose federated learning with consensus-oriented generation (FedCOG) FedCOG consists of two key components at the client side: complementary data generation and knowledge-distillation-based model training. Experiments on classical and real-world FL datasets show that FedCOG consistently outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-12-10T18:49:59Z)
• FedFed: Feature Distillation against Data Heterogeneity in Federated Learning [88.36513907827552]
  Federated learning (FL) typically faces data heterogeneity, i.e., distribution shifting among clients. We propose a novel approach called textbfFederated textbfFeature textbfdistillation (FedFedFed) FedFed partitions data into performance-sensitive features (i.e., greatly contributing to model performance) and performance-robust features (i.e., limitedly contributing to model performance) Comprehensive experiments demonstrate the efficacy of FedFed in promoting model performance.
  arXiv  Detail & Related papers  (2023-10-08T09:00:59Z)
• Diversity-enhancing Generative Network for Few-shot Hypothesis Adaptation [135.80439360370556]
  We propose a diversity-enhancing generative network (DEG-Net) for the FHA problem. It can generate diverse unlabeled data with the help of a kernel independence measure: the Hilbert-Schmidt independence criterion (HSIC)
  arXiv  Detail & Related papers  (2023-07-12T06:29:02Z)
• Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
  We introduce a new and robust version of the Gromov-Wasserstein (GW) distance called RGW. RGW features optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set. We demonstrate the effectiveness of RGW on real-world graph learning tasks, such as subgraph matching and partial shape correspondence.
  arXiv  Detail & Related papers  (2023-02-09T12:57:29Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Graph Federated Learning for CIoT Devices in Smart Home Applications [23.216140264163535]
  We propose a novel Graph Signal Processing (GSP)-inspired aggregation rule based on graph filtering dubbed G-Fedfilt'' The proposed aggregator enables a structured flow of information based on the graph's topology. It is capable of yielding up to $2.41%$ higher accuracy than FedAvg in the case of testing the generalization of the models.
  arXiv  Detail & Related papers  (2022-12-29T17:57:19Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
  The Gromov-Wasserstein (GW) formulates a node graph between the structured data based on optimal transportation datasets. We take inspiration from the connection with the assignment problem, and propose the Gromov-Wasserstein discrepancy as a surrogate of GW.
  arXiv  Detail & Related papers  (2022-05-12T02:10:56Z)
• On a linear fused Gromov-Wasserstein distance for graph structured data [2.360534864805446]
  We propose a novel distance between two graphs, named linearFGW, defined as the Euclidean distance between their embeddings. The advantages of the proposed distance are twofold: 1) it can take into account node feature and structure of graphs for measuring the similarity between graphs in a kernel-based framework, 2) it can be much faster for computing kernel matrix than pairwise OT-based distances.
  arXiv  Detail & Related papers  (2022-03-09T13:43:18Z)
• Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters [2.169919643934826]
  We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss. We propose a predictive model relying on a FGW barycenter whose weights depend on inputs.
  arXiv  Detail & Related papers  (2022-02-08T12:15:39Z)
• Heterogeneous Federated Learning via Grouped Sequential-to-Parallel Training [60.892342868936865]
  Federated learning (FL) is a rapidly growing privacy-preserving collaborative machine learning paradigm. We propose a data heterogeneous-robust FL approach, FedGSP, to address this challenge. We show that FedGSP improves the accuracy by 3.7% on average compared with seven state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-01-31T03:15:28Z)
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs [77.34726150561087]
  We introduce the R package for causal discovery and causal effect estimation from observational data. Our implementation scales efficiently with the number of observations and, whenever the DAGs are sufficiently sparse, the number of variables in the dataset. We then illustrate the main functions and algorithms on both real and simulated datasets.
  arXiv  Detail & Related papers  (2022-01-28T09:30:32Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.