Mathematical Background

Full report

On this page

Wasserstein vs. Gromov-Wasserstein vs. Fused Gromov-Wasserstein. In classical optimal transport (OT), the Wasserstein distance compares two probability distributions by minimizing the cost of moving “mass” between points under a cost metric on the feature space. The Gromov-Wasserstein (GW) distance instead compares two metric measure spaces by aligning their intrinsic distance matrices: it solves a quadratic assignment problem that matches points so as to minimize differences in pairwise distances (structure). The Fused Gromov-Wasserstein (FGW) distance jointly optimizes both feature similarity and structural similarity: it introduces a trade-off parameter $\alpha\in[0,1]$ so that the objective is $$(1-\alpha)\langle M,T\rangle + \alpha\sum_{i,j,k,l}|C_s(i,k)-C_t(j,l)|^q\,T_{ik}T_{jl},$$ minimizing over couplings $T$ subject to marginals. Here $M_{ik}=d(a_i,b_k)^q$ is the feature cost, and $C_s,C_t$ are structural (graph) distance matrices. If $\alpha=0$, FGW reduces to pure Wasserstein on features; if $\alpha=1$, it becomes standard GW on structure. (We verify for each solver whether $\alpha$ weights structure or features, since some libraries define it oppositely.)

Feature and structural terms. In FGW, the feature term $(1-\alpha)\langle M,T\rangle$ encourages matching nodes with similar attributes, while the structural term $\alpha \sum_{i,j,k,l}|C_s(i,k)-C_t(j,l)|^qT_{ik}T_{jl}$ encourages preservation of graph distances. One typically uses squared loss ($q=2$) for stability, but KL or other divergences can also be used. The choice of structural matrix $C$ depends on graph representation: it could be the adjacency matrix, shortest-path distance matrix, or another graph kernel. Each choice emphasizes different aspects of structure (e.g. direct connectivity vs. global distances). Likewise node mass choices (the marginal distributions $p,q$) are often uniform (all nodes equal mass) but can be weighted by node importance (e.g. centrality or degree).

Marginal constraints and balanced vs. unbalanced variants. Standard FGW assumes balanced OT: the total source mass equals target mass, and every unit of mass is transported. In practice, graphs may differ in size or have extra nodes, so unbalanced or partial FGW is needed. For partial FGW, one specifies a fraction of mass $m$ to transport or adds “dummy” nodes: the solver then finds a coupling that may leave some nodes unmatched, effectively modeling insertions/deletions. Some solvers use a relaxation penalty instead (semi-relaxed FGW) or incorporate unbalanced OT penalties (e.g. KL terms on marginals) to allow mass differences. The POT library, for example, provides partial_fused_gromov_wasserstein with an extra mass parameter and dummy nodes. We will ensure our design accounts for unbalanced cases (e.g. different graph sizes) by supporting partial-FGW parameters.

Optimization and convergence. Computing FGW is a non-convex quadratic assignment problem, generally NP-hard in the worst case. Practical solvers use iterative methods. The standard approach (e.g. in POT) is a Conditional Gradient (CG) or projected-gradient method on the quadratic cost. Entropic regularization (Sinkhorn) can also be applied: adding $-\varepsilon H(T)$ makes the problem convex-ish and tractable via Sinkhorn iterations, but at the cost of bias. In POT’s entropic_fused_gromov_wasserstein, for example, the optimized objective is $(1-\alpha)\langle M,T\rangle + \alpha\sum L(C_s,C_t)\,T T - \varepsilon H(T)$. Entropic solvers converge rapidly and are stable for large graphs, but can yield only approximate distances, and if not fully converged may violate marginal constraints (even producing negative FGW loss). CG solvers (without entropy) preserve exact marginals by construction, but require line-search and may converge slowly or get stuck in local minima. In practice, a small regularization ($\varepsilon$) and robust initialization (e.g. Sinkhorn warm-start or repeated random restarts) help.

Precision, stability, complexity. FGW involves $\mathcal{O}(n_s n_t)$ memory for the coupling and $\mathcal{O}(n_s^2 n_t^2)$ work per full gradient evaluation (the double sum over $i,j,k,l$) if done naively. Efficient solvers exploit structure: the CG method implements the cost gradient via matrix multiplications rather than explicit 4D sums, bringing complexity roughly to $\mathcal{O}((n_s+n_t)^3)$ per iteration. Still, for graphs beyond a few thousand nodes this becomes costly. Multi-threading and GPU-acceleration can speed up the inner loops, but floating-point operations can then become non-deterministic (see Reproducibility below). Numerical stability requires careful handling of precision, especially if using float types. We will use double-precision in transmission, but note that some libraries (e.g. GPU versions) may use float32 for performance.

Meaning and limitations of the coupling. The solver returns a soft coupling matrix $T$, where $T_{ik}$ indicates the “mass” transported from source node $i$ to target node $k$. For balanced FGW, $T$ is a joint probability distribution over nodes with marginals $p$ and $q$. It is not in general a permutation matrix: nodes can split mass to multiple matches. Consequently, interpreting $T$ directly as a one-to-one alignment (e.g. “node $i$ maps to $\arg\max_k T_{ik}$”) is unsafe because multiple $i$’s may prefer the same $k$ and vice versa. Instead, we will deterministically project $T$ into discrete matchings (see Deterministic Projection). Also, a low FGW distance or strong coupling does not guarantee graph isomorphism; it only indicates an approximate alignment minimizing the FGW criterion. Finally, with entropic FGW the returned distance may slightly violate metric properties, so we interpret outputs as heuristic alignment scores rather than exact distances.

In summary, FGW blends feature and structure costs. We will use balanced FGW by default but allow partial/unbalanced cases (supporting dummy nodes or relaxation). Key solver parameters include the trade-off $\alpha$, regularization $\varepsilon$, and convergence tolerances. The returned coupling $T$ must be treated carefully (soft assignments). All mathematical claims above are drawn from FGW theory and solver docs.

Solver and Technology Comparison

We consider several integration approaches for the FGW solver into a .NET ecosystem:

• In-process .NET implementation. No mature FGW library exists in C#/.NET. Re-implementing FGW from scratch in C# would be a major effort (solving a nonconvex program) and would duplicate work done in existing libraries. It might avoid cross-language overhead, but it risks bugs and lagging features.

• Python microservice. The leading FGW solver (POT library) is in Python (with a C++ core). We could deploy a Python-based microservice exposing a gRPC endpoint. Benefits: reuse state-of-the-art algorithms, frequent updates (POT is under active development), and GPU support. Downsides: managing a Python service in production (containerization, dependencies, OOMs in Python, GIL concurrency) and data marshalling overhead. However, Python has matured gRPC support and can easily load POT to compute FGW. This approach decouples the solver from the .NET stack.

• C++ microservice or P/Invoke. POT’s core is in C++, and one could compile it to a standalone library and either call it via P/Invoke (DLL) or wrap it in a gRPC server in C++. This could yield high performance and avoid Python’s interpreter overhead. However, POT’s code is not designed as a drop-in DLL, and binding its dependencies (Eigen, KeOps, BLAS) would be complex. A pure C++ solver (if available) might be faster but we have no off-the-shelf FGW-only C++ library to leverage. Writing one would be a large research project. P/Invoke also complicates deployment (native binaries per platform).

• Portable runtime (ONNX, ML). FGW is an optimization problem, not a fixed graph neural net or static function, so exporting to ONNX is not applicable. One could train a neural model to approximate FGW, but the task specifies numerical solver, so this is out of scope.

• Batch vs. synchronous RPC. The orchestration service is ASP.NET Core. We can either queue alignment jobs (batch) or call the solver synchronously. Since alignments are often offline but may need deadlines, a synchronous RPC with cancellation support via gRPC is suitable. If high throughput is needed, we can consider batching multiple graph pairs per call. However, batching adds latency and complexity. Instead, we will use per-request (unary or stream) with timeouts and allow the client to retry if needed.

Recommendation: We recommend running the FGW solver as an external microservice (in Python or C++) accessed via gRPC. This cleanly separates the .NET orchestrator from the specialized numerical code, and allows independent scaling. In-process .NET is not practical given lack of library support, and P/Invoke risks stability issues. A Python microservice using the POT library (or similar) is likely easiest to implement and extend. The .NET service sends a gRPC request with graph data and configuration; the solver responds with the coupling. We will containerize the solver (Docker or Kubernetes) with resource limits to mitigate memory attacks. Observability: gRPC interceptors and logging will record call counts, latencies, and statuses. We set RPC deadlines and propagate cancellations: if the ASP.NET Core request is aborted (deadline exceeded or client disconnects), we cancel the solver call. A retry policy (e.g. using Polly) can automatically retry on transient and idempotent failures (note: solver should be deterministic so retry is safe). Dead-lettering can capture persistent failures for manual analysis.

Mermaid Component Diagram: The architecture is summarized below:

flowchart LR
    subgraph A[Agent Memory Platform (C#)]
        B[Graph Preparation]
        C[FGW gRPC Client]
        D[Projection & Edit Plan]
        E[Data Store]
    end
    subgraph S[FGW Solver Service]
        F[Graph Merge & Conversion]
        G[FGW Algorithm Solver]
    end
    B --> C
    C -- gRPC --> G
    G -- Coupling + metadata --> D
    D --> E
    E --> B

Graph Serialization (gRPC Contract)

We define a versioned Protocol Buffers service and messages to transmit graph data and solver config. Key requirements are efficient sparse representation and forward/backward compatibility. We use proto3 syntax with explicitly versioned packages. Below is an outline of the .proto definitions:

syntax = "proto3";
package transport.v1;

// Versioning note: we maintain backwards compatibility using reserved fields when evolving.

// Enum for FGW variants
enum FgwVariant {
  BALANCED = 0;       // standard balanced FGW
  PARTIAL = 1;        // partial/unbalanced FGW
  SEMI_RELAXED = 2;   // one-sided relaxation, etc.
}

// Request message for a FGW alignment
message FgwRequest {
  string request_id = 1;         // unique ID for tracing
  string source_graph_id = 2;
  string target_graph_id = 3;
  uint32 schema_version = 4;     // for GraphDefinition versions
  GraphDefinition source_graph = 5;
  GraphDefinition target_graph = 6;
  FgwConfig config = 7;
  // Optional precomputed feature-cost entries: (source_index, target_index, cost)
  repeated FeatureCostEntry feature_cost = 8;
  uint64 seed = 9;
  repeated byte provenance_hash = 10; // hash of input metadata
}

// Graph data (sparse)
message GraphDefinition {
  // Node masses: distributions p and q
  repeated uint32 node_ids = 1;        // 0-based node indices
  repeated double node_mass = 2;       // mass for each node_id
  // Node features (sparse): for graph attributes if needed
  repeated FeatureVector node_features = 3;
  // Structural edges (sparse adjacency or distance)
  repeated Edge edges = 4;
}

// Sparse feature vector for a single node
message FeatureVector {
  uint32 node_id = 1;
  repeated uint32 indices = 2;  // feature indices
  repeated double values = 3;   // feature values
}

// Sparse edge (or distance) entry
message Edge {
  uint32 src = 1;
  uint32 dst = 2;
  double weight = 3;
}

// Optional precomputed feature-cost (cross-graph)
message FeatureCostEntry {
  uint32 src_node = 1;
  uint32 dst_node = 2;
  double cost = 3;
}

// Solver configuration parameters
message FgwConfig {
  FgwVariant variant = 1;
  double alpha = 2;
  double epsilon = 3;      // entropic regularization
  uint32 max_iter = 4;
  double tolerance = 5;
  double mass_reg = 6;     // for partial FGW: total mass or ratio
  // Additional solver flags (e.g. symmetric structures)
  bool symmetric = 7;
}

Design notes:

• We use explicit versioning (transport.v1) and include schema_version and request_id. All message numbers should not be changed once deployed; deprecated fields should use reserved according to protobuf best practices.
• Graphs are sent once per request (two GraphDefinition messages). For very large graphs, we can support client-streaming where the client first sends a header with IDs and config, then streams chunks of node/edge data. An alternative is compressing repeated fields or using chunked bytes. gRPC best practices suggest splitting messages over ~64KB chunks if needed. The service could define a streaming RPC for graph data if unary messages exceed limits. Here we outline a unary design for simplicity.
• Sparse representation: node masses and feature vectors use index/value pairs, and Edge lists connections. We assume undirected graphs stored with one direction or symmetric entries.
• FeatureCostEntry allows sending a precomputed cost matrix $M_{ik}$. If omitted, the solver computes $M$ from node_features.
• We include a 64-bit seed for determinism, and a provenance_hash (e.g. SHA256) of all input, for audit.
• Enumeration FgwVariant distinguishes balanced vs partial FGW, etc., so the solver knows which algorithm branch to use.

RPC method:

service FgwSolver {
  // Unary or streaming request of graph data
  rpc ComputeFgw(FgwRequest) returns (FgwResponse);
}

We will configure the service for deadlines and allow cancellation. Large data could use HTTP/2 flow control tuning. Messages use fixed-size types (uint32, double) to ensure predictable representation. We rely on protobuf’s default (network byte order) and IEEE754 double. We should document endianness (big-endian on the wire) and float format (IEEE754).

Streaming vs Unary: For most use cases we expect graphs to fit within reasonable message sizes after compression. If needed, we can switch to client-streaming: e.g. streaming chunks of GraphDefinition or bytes. We would then validate chunk order by sequence numbers in the payload and use checksums on each chunk for integrity. For versioning, we follow protobuf rules: older clients reading new fields ignore unknown fields; new clients reading old messages get default values.

Solver Response

The gRPC response returns the coupling and diagnostics. Example response schema:

message FgwResponse {
  string request_id = 1;
  double objective = 2;       // total FGW cost
  double feature_cost = 3;
  double structural_cost = 4;
  bytes coupling_hash = 5;    // hash of coupling for integrity
  repeated CouplingEntry coupling = 6;  // sparse representation
  uint32 iterations = 7;
  bool converged = 8;
  double solve_time = 9;      // seconds
  string solver_name = 10;
  string solver_version = 11;
  repeated SolverWarning warnings = 12;
  repeated CandidateAssignment candidates = 13; // optional projections
}

// Sparse coupling entry
message CouplingEntry {
  uint32 src = 1;
  uint32 dst = 2;
  double mass = 3; // T_{src,dst}
}

// Candidate discrete assignment (optional projection results)
message CandidateAssignment {
  repeated uint32 source_nodes = 1;
  repeated uint32 target_nodes = 2;
  double score = 3;
}

// Structured status details for errors (using google.rpc.Status)
message SolverWarning {
  string code = 1;
  string message = 2;
}

Content:

• We return the full coupling matrix as a sparse list of (i,k,T_{ik}). If graphs are small, this list may be dense; for larger graphs many entries may be negligible and omitted. The response includes a hash of the coupling (coupling_hash) for later integrity check.
• We break out the objective into feature and structural components for diagnostics (these can be computed by rerunning $(1-\alpha)\<M,T\>$ and $\alpha\cdot\text{GW-term}$).
• Iteration count and a boolean converged indicate solver progress. Warnings can flag issues (e.g. numeric underflow, early termination, non-convergence). We set converged=false if iterations hit the limit without meeting tolerance.
• We include solver_name and solver_version (e.g. “POT 0.9.7”) so the client can check compatibility. The response has the same request_id for tracing.
• If the request asked for discrete assignments (candidates), we include them here: each candidate has parallel lists of source and target node IDs (matched by index) and a score (e.g. sum of assigned coupling or a normalized metric).
• Errors (bad input, resource limits) are returned via gRPC status codes with structured details (we define a SolverWarning to attach error codes). For example, mismatched dimensions could yield an INVALID_ARGUMENT status with code "DimensionMismatch".

All fields in responses are well-defined (no free-text except message fields) to allow robust parsing. We will ensure no sensitive data is returned; only IDs and metrics. Typical sizes: the coupling list could be $O(n_s n_t)$ entries; streaming may be needed if graphs are very large.

C# Orchestration (Client and Data Models)

Below we sketch C# code to build the request, call the gRPC service, and handle the response. We define data classes with [Display(Name="…")] attributes as requested. (In a real implementation, these might wrap the generated proto classes or use partial classes for metadata.)

using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Threading;
using System.Threading.Tasks;
using Grpc.Core;
using Grpc.Net.Client;
using Transport.V1; // generated from protobuf

/// <summary>
/// Represents node mappings (soft assignments) returned from the FGW solver.
/// </summary>
public class FgwCouplingEntry
{
    [Display(Name = "Source Node")]
    public uint Src { get; set; }
    [Display(Name = "Target Node")]
    public uint Dst { get; set; }
    [Display(Name = "Transported Mass")]
    public double Mass { get; set; }
}

/// <summary>
/// Configuration parameters for the FGW solver.
/// </summary>
public class FgwConfig
{
    [Display(Name = "FGW Variant")]
    public FgwVariant Variant { get; set; } = FgwVariant.Balanced;

    [Display(Name = "Alpha (feature/structure tradeoff)")]
    public double Alpha { get; set; } = 0.5;

    [Display(Name = "Entropic Regularization Epsilon")]
    public double Epsilon { get; set; } = 1e-3;

    [Display(Name = "Max Iterations")]
    public uint MaxIter { get; set; } = 1000;

    [Display(Name = "Tolerance")]
    public double Tolerance { get; set; } = 1e-6;

    [Display(Name = "Partial FGW Total Mass")]
    public double MassReg { get; set; } = 1.0;

    [Display(Name = "Assume symmetric structure")]
    public bool Symmetric { get; set; } = true;
}

/// <summary>
/// Represents a sparse graph with node masses, features, and edges.
/// </summary>
public class GraphDefinition
{
    [Display(Name = "Graph Identifier")]
    public string GraphId { get; set; }

    [Display(Name = "Node Identifiers")]
    public uint[] NodeIds { get; set; }

    [Display(Name = "Node Masses")]
    public double[] NodeMasses { get; set; }

    [Display(Name = "Feature Vectors")]
    public List<FeatureVector> Features { get; set; }

    [Display(Name = "Edges")]
    public List<GraphEdge> Edges { get; set; }
}

/// <summary>
/// Sparse feature vector for a node.
/// </summary>
public class FeatureVector
{
    [Display(Name = "Node ID")]
    public uint NodeId { get; set; }

    [Display(Name = "Feature Indices")]
    public uint[] Indices { get; set; }

    [Display(Name = "Feature Values")]
    public double[] Values { get; set; }
}

/// <summary>
/// Sparse edge (undirected) in the graph.
/// </summary>
public class GraphEdge
{
    [Display(Name = "Source Node")]
    public uint Src { get; set; }

    [Display(Name = "Destination Node")]
    public uint Dst { get; set; }

    [Display(Name = "Edge Weight")]
    public double Weight { get; set; }
}

public class FgwClient
{
    private readonly FgwSolver.FgwSolverClient _grpcClient;
    private readonly TimeSpan _timeout = TimeSpan.FromSeconds(60);

    public FgwClient(string solverAddress)
    {
        var channel = GrpcChannel.ForAddress(solverAddress);
        _grpcClient = new FgwSolver.FgwSolverClient(channel);
    }

    /// <summary>
    /// Sends the FGW request and returns the coupling entries.
    /// </summary>
    /// <param name="srcGraph">Source graph definition.</param>
    /// <param name="tgtGraph">Target graph definition.</param>
    /// <param name="config">Solver configuration.</param>
    /// <param name="cancellation">Cancellation token.</param>
    /// <returns>List of coupling entries (sparse matrix).</returns>
    /// <exception cref="RpcException">Thrown if gRPC call fails or times out.</exception>
    public async Task<List<FgwCouplingEntry>> ComputeAsync(
        GraphDefinition srcGraph,
        GraphDefinition tgtGraph,
        FgwConfig config,
        CancellationToken cancellation = default)
    {
        // Build request
        var request = new FgwRequest
        {
            RequestId = Guid.NewGuid().ToString(),
            SourceGraphId = srcGraph.GraphId,
            TargetGraphId = tgtGraph.GraphId,
            SchemaVersion = 1,
            Config = new FgwConfig
            {
                Variant = (Transport.V1.FgwVariant)config.Variant,
                Alpha = config.Alpha,
                Epsilon = config.Epsilon,
                MaxIter = config.MaxIter,
                Tolerance = config.Tolerance,
                MassReg = config.MassReg,
                Symmetric = config.Symmetric
            },
            Seed = (ulong)new Random(config.Seed.GetHashCode()).Next()
        };

        // Copy node masses
        for (int i = 0; i < srcGraph.NodeIds.Length; i++)
        {
            request.SourceGraph.NodeIds.Add(srcGraph.NodeIds[i]);
            request.SourceGraph.NodeMass.Add(srcGraph.NodeMasses[i]);
        }
        for (int j = 0; j < tgtGraph.NodeIds.Length; j++)
        {
            request.TargetGraph.NodeIds.Add(tgtGraph.NodeIds[j]);
            request.TargetGraph.NodeMass.Add(tgtGraph.NodeMasses[j]);
        }
        // Copy edges (assuming undirected, sender can ensure both directions or only one side)
        foreach (var e in srcGraph.Edges)
        {
            request.SourceGraph.Edges.Add(new Edge { Src = e.Src, Dst = e.Dst, Weight = e.Weight });
        }
        foreach (var e in tgtGraph.Edges)
        {
            request.TargetGraph.Edges.Add(new Edge { Src = e.Src, Dst = e.Dst, Weight = e.Weight });
        }
        // Optionally include feature vectors or costs if needed (omitted here for brevity)

        // Validate dimensions
        if (srcGraph.NodeIds.Length != srcGraph.NodeMasses.Length ||
            tgtGraph.NodeIds.Length != tgtGraph.NodeMasses.Length)
        {
            throw new ArgumentException("Node IDs and masses length mismatch");
        }

        // Setup deadline and call
        var callOptions = new CallOptions(deadline: DateTime.UtcNow.Add(_timeout), cancellationToken: cancellation);
        FgwResponse response;
        try
        {
            response = await _grpcClient.ComputeFgwAsync(request, callOptions);
        }
        catch (RpcException ex) when (ex.StatusCode == StatusCode.DeadlineExceeded)
        {
            // Timeout handling
            throw new TimeoutException("FGW solver call timed out", ex);
        }

        // Validate response
        if (response == null || !response.Converged)
        {
            throw new InvalidOperationException("FGW solver did not converge");
        }

        // Parse coupling
        var coupling = new List<FgwCouplingEntry>();
        foreach (var ce in response.Coupling)
        {
            coupling.Add(new FgwCouplingEntry
            {
                Src = ce.Src,
                Dst = ce.Dst,
                Mass = ce.Mass
            });
        }

        // Telemetry/logging (example)
        Console.WriteLine($"FGW completed in {response.Iterations} iterations, time {response.SolveTime}s");
        return coupling;
    }
}

Explanation: This C# code constructs the FgwRequest, sets the deadline, and sends it. Public properties all have [Display(Name="...")], with names derived from the property (omitting “Id” suffix as instructed: e.g. GraphId becomes “Graph Identifier”). We include XML comments for methods and parameters. We propagate CancellationToken into CallOptions. We catch DeadlineExceeded to retry or fail. We would apply a retry policy (e.g. exponential backoff) around ComputeAsync, but only for idempotent errors (deadline or transient network faults), not for invalid arguments. The code verifies the solver’s converged flag. Logging/telemetry calls could use ILogger or tracing to record solution time, iterations, etc. Finally, we convert the sparse coupling to a list of entries.

Deterministic Projection

The soft coupling $T$ must be turned into one or more discrete matchings. We compare methods:

• Maximum-weight bipartite matching (Hungarian). Interpret $T_{ik}$ as weights; solve the assignment problem maximizing $\sum_i T_{i,\pi(i)}$. For equal-sized graphs, this yields the highest-total-mass 1-1 mapping. With unequal sizes, we add dummy nodes to make the cost matrix square (with zero costs for dummy matches) and solve. The Hungarian algorithm runs in polynomial time (typically $O(n^3)$), but implementing it from scratch is complex. We can use an existing library or adapt an open-source C# implementation. This ensures global optimal discrete assignment.

• Greedy matching. Sort all $(i,k)$ by descending $T_{ik}$. Iterate: if source $i$ and target $k$ are both unmatched, match them; otherwise skip. Continue until all possible or end. This is deterministic (tie-broken by index order) and $O(n^2\log n)$ to sort. It is not globally optimal, but simple.

• Mutual nearest matching. For each source $i$, let $k=\arg\max_jT_{ij}$, and for each target $k$, let $i=\arg\max_iT_{ik}$. If $i$’s best is $k$ and $k$’s best is $i$, match them. Remove them and repeat. This is very fast $O(n^2)$ but may leave some nodes unmatched even if better global matches exist. We must break ties deterministically (e.g. lowest-index priority).

• Top-k branching. We could generate multiple assignments by branching choices on ambiguous matches. For example, find the top-$k$ augmenting trees from a seed matching. This is complex combinatorics and we defer it.

For stability and completeness, we recommend Hungarian assignment (with dummy nodes) as the default projection. It gives a single best mapping; we can also output it as a “score” and then relax it to find alternate candidates if needed (e.g. by zeroing out a matched pair and rerunning).

Below is illustrative C# code using a greedy algorithm (for brevity). In practice, one would replace GreedyMatch with a robust Hungarian solver for production. We ensure deterministic ties by sorting by $(T_{ik},i,k)$ lexicographically.

/// <summary>
/// Projects a soft coupling matrix to a discrete matching using greedy highest-mass first.
/// </summary>
/// <param name="coupling">Sparse coupling as list of entries (src, dst, mass).</param>
/// <param name="numSource">Number of source nodes.</param>
/// <param name="numTarget">Number of target nodes.</param>
/// <returns>List of matched pairs (src, dst).</returns>
public static List<(int Source, int Target)> GreedyProjection(
    List<FgwCouplingEntry> coupling, int numSource, int numTarget)
{
    // Sort entries by descending mass; tie-break by Source then Target.
    coupling.Sort((a, b) => {
        int cmp = b.Mass.CompareTo(a.Mass);
        if (cmp != 0) return cmp;
        cmp = a.Src.CompareTo(b.Src);
        if (cmp != 0) return cmp;
        return a.Dst.CompareTo(b.Dst);
    });

    var matchedSource = new bool[numSource];
    var matchedTarget = new bool[numTarget];
    var mapping = new List<(int,int)>();

    foreach (var entry in coupling)
    {
        int i = (int)entry.Src, k = (int)entry.Dst;
        if (!matchedSource[i] && !matchedTarget[k] && entry.Mass > 0)
        {
            // Match i -> k
            mapping.Add((i, k));
            matchedSource[i] = true;
            matchedTarget[k] = true;
        }
    }
    return mapping;
}

Graph edit operations: Given a discrete mapping, we can infer graph edits. For each source node not matched, we generate a delete-node operation; for each target node not matched, an insert-node; for each matched pair $(i \to k)$, we compare their adjacency: if source $i$ has a neighbor $j$ matched to a node $\ell \neq$ neighbor of $k$, we can schedule an delete-edge or insert-edge to align the structures. In practice, building the full edit script is graph-specific and potentially large. We would validate the edit plan by applying it to the source graph and checking isomorphism with target (for the mapped subgraphs). Due to space, we omit full code for edit generation, but one would iterate over all edges and node matches to record the minimal edit operations.

Reproducibility and Validation

To enable full reproducibility, we capture a “reproducibility envelope” of metadata with each alignment result. This includes:

• Input hashes: a cryptographic hash (e.g. SHA256) of the serialized graphs and parameters, so identical inputs can be detected and matched.
• Schema versions: graph data schema version, feature schema, etc.
• Solver image digest and version: e.g. container image SHA and solver version string.
• Numerical library versions: BLAS/LAPACK, CUDA/cuDNN versions if GPU, etc. (if applicable).
• Hardware info: CPU architecture, number of threads, GPU model.
• Precision: float64 vs float32, etc.
• Random seed: as provided in the request.
• Solver parameters: all FGWConfig fields (alpha, epsilon, etc).
• Thread and environment settings: number of solver threads, any OpenMP settings.

We also record timing (CPU vs wall time). All this is stored or logged alongside results (but not sent as part of the algorithm output).

In practice, bitwise reproducibility in numerical computation is challenging. Floating-point arithmetic is non-associative, and parallel hardware (multi-thread CPU or GPU) can introduce nondeterminism. For example, parallel reduction sums may vary by thread scheduling. Even the order of operations in a Sinkhorn iteration or CG step can differ across runs. Ensuring identical results across CPU and GPU is generally impossible without special deterministic algorithms (e.g. fixed reduction trees or single-threaded execution). Therefore, we specify that the solver container should run in a controlled environment: for instance, fixing the number of threads and using deterministic summation methods. We note that mixing CPU and GPU may break reproducibility. In validation tests, we will require that the same environment (same code, same hardware architecture) yields identical outputs given the seed.

Validation test suite: We create unit tests on toy graphs where the FGW alignment is known. Examples:

• Two identical graphs (any structure): the optimal coupling is the identity, distance = 0.
• One-node vs one-node: trivial.
• Two graphs with a clear permutation (e.g. chains of 3 nodes with distinct features): test that the mapping recovers the permutation.
• Partial matching: e.g. source has an extra isolated node; check that FGW marks it as matched to a dummy (mass not transported).
• Balanced vs partial variant: verify that setting mass/matching differently gives expected ignore vs forced match outcomes.

Each test will compute FGW via our service and then check the returned discrete mapping and edit plan against the analytically known solution. We also verify that repeated calls with the same seed give identical $T$ and projections (bitwise match).

Operations and Security

We must handle malicious or extreme inputs carefully:

• Dimension checks: If the client provides inconsistent graph sizes (e.g. SourceGraph.NodeIds.Length != NodeMasses.Length), we return an INVALID_ARGUMENT error. If the graph exceeds a pre-set maximum node count (to limit O($n^4$) work), we return RESOURCE_EXHAUSTED.
• Mass constraints: We enforce that $\sum p = \sum q$ for balanced FGW; if not, and the variant is balanced, return an error. For partial/unbalanced, we accept mismatched sums.
• Value checks: Reject NaN or infinite costs, masses, weights. All double fields are checked to be finite.
• Sparse integrity: Validate that edge lists reference valid node IDs. Remove duplicate edges or self-loops (or reject).
• Oversized requests: We set gRPC max message sizes on both server and client (per ASP.NET Core guidelines). If a request is too large, it triggers a RESOURCE_EXHAUSTED or INVALID_ARGUMENT error. We support HTTP/2 compression to reduce payload, but also size limits.
• Solver isolation: The solver runs in a container with strict resource limits (CPU, memory). We also can run it under a sandbox user, with ulimits to prevent fork bombs or memory exhaustion.
• Dead-letter handling: If a request repeatedly fails (e.g. due to bad format), it can be routed to a dead-letter queue for manual inspection. Valid errors use gRPC status codes and no private data. The client should not send sensitive graph contents to the solver if confidentiality is a concern (the architecture can use encryption/TLS if needed).
• Security updates: The solver image should be built from pinned dependencies (e.g. specific Python version, library hashes). Supply-chain best practices (hashing images, scanning for vulnerabilities) are applied.
• Logging and audit: All requests and responses (or at least their metadata/hashes) are logged with timestamps and request IDs. Only non-sensitive metrics (dimensions, success/fail) are logged to avoid leaking data.
• Data minimization: We transmit only numeric data needed for FGW. Any large raw data (e.g. original feature objects) is not sent if not needed. We keep provenance hashes, not full content, in logs.

Finally, the orchestration code and solver must treat all numerical output as untrusted: we validate the coupling matrix shape and marginals upon receipt. We never blindly trust the highest coupling per row as a match (we do the full projection algorithm).

The overall system is built on .NET 8/9 and ASP.NET Core with gRPC, using UTC timestamps everywhere. By combining rigorous input validation, resource limiting, structured errors, and audit logging, we address the key security and operational constraints.

Summary and Open Questions

We have outlined the FGW optimization, integration architecture, and end-to-end design. Key deliverables include:

• A mathematical description of FGW (feature vs structure costs).
• A recommendation to use a Python (POT) or C++ solver in a gRPC microservice.
• A versioned protobuf contract (FgwRequest, FgwResponse).
• C# client code for request building and RPC calling, with [Display] attributes.
• A projection algorithm to produce deterministic discrete alignments from the coupling.
• A list of reproducibility and security requirements and mitigations, citing best practices.

Open research questions: Efficiently solving FGW for very large graphs (10k+ nodes) remains challenging. Methods like entropic Sinkhorn scale better but need careful tuning of $\varepsilon$. Finding robust initialization or warm-start strategies (e.g. using graph embedding or network flow relaxations) is an active area. On the projection side, enumerating multiple high-quality matchings (beyond the optimum) is nontrivial; future work could adapt the Murty’s algorithm for $k$-best assignments. Another open question is whether one can certify the quality of the found coupling (e.g. dual bounds) for a nonconvex FGW. Lastly, extending FGW to streaming or dynamic graphs (where graphs evolve over time) invites additional design of incremental alignment algorithms.

References: The above is based on foundational OT and FGW literature, the POT library documentation, gRPC/protobuf best practices, and numerical reproducibility studies. Each claim and design choice is drawn from these sources or standard practice.