PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

Lutz Oettershagen, Honglian Wang, Aristides Gionis

arXiv:2608.29635v1cs.LGcs.SI

TL;DR

Unsupervised hypergraph alignment seeks node correspondences from structure alone, but existing higher-order and graph-reduction representations trade fidelity, scalability, and problem size. FALCON uses filtration-induced co-occurrence views with one shared multi-scale GW plan, and experiments report robustness to structural noise with performance generally matching or exceeding strong baselines.

  • Problem

    Unsupervised hypergraph alignment must recover node correspondences from higher-order structure without features, labels, side information, or seed matches, while existing representations have important computational or structural trade-offs.

  • Method

    FALCON constructs filtration-induced clique-based co-occurrence views on the original nodes and jointly aligns them with one shared multi-scale GW transport plan.

  • Results

    FALCON is robust to structural perturbations and generally matches or outperforms strong graph- and hypergraph-alignment baselines on controlled real-world hypergraph benchmarks.

  • Takeaways & Limitations

    Multi-scale filtration preserves scale-separated co-occurrence evidence while producing one globally consistent node correspondence within a pairwise optimal-transport framework.

Abstract

from arXiv · show

We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.

I. INTRODUCTION

The paper frames unsupervised hypergraph alignment as recovering node correspondences from higher-order structure alone, then introduces FALCON to preserve multi-scale evidence without auxiliary hyperedge nodes. Controlled perturbation experiments show robustness and generally competitive or superior performance against graph- and hypergraph-alignment baselines.

  • Unsupervised alignment must recover an unknown node correspondence using hypergraph structure without features, labels, side information, or seed matches.
  • Direct higher-order methods preserve hyperedge interactions but can be computationally demanding, while clique and bipartite reductions impose complementary representation trade-offs.Clique reductions retain the original nodes but collapse hyperedge evidence; bipartite reductions preserve incidence while adding auxiliary hyperedge nodes.
  • On controlled perturbation benchmarks derived from real-world hypergraphs, FALCON is robust to structural noise and generally matches or outperforms strong alignment baselines.
  • FALCON replaces one collapsed clique graph with multiple filtration-induced, scale-separated co-occurrence views while retaining the original node set.
  • FALCON jointly aligns all filtration levels with one shared GW coupling, producing a globally consistent correspondence across induced views.The paper identifies the shared-coupling formulation and filtration-induced relational channels as its key distinction, rather than a new GW solver.

III. PRELIMINARIES

The preliminaries define hypergraphs and the unrestricted alignment task, review clique and bipartite reductions, and describe GW transport as a soft correspondence later discretized by assignment.

  • A hypergraph consists of nodes and non-empty hyperedges, with k-uniform hypergraphs having all hyperedges of cardinality k; ordinary graphs are 2-uniform hypergraphs.
  • Unsupervised alignment estimates a bijection between equal-sized source and target node sets using only observed hypergraph structures and no features, labels, side information, or seed matches.
  • Clique representation preserves the original node set but is lossy because it converts higher-order hyperedges into pairwise edges, allowing distinct hypergraphs to share a clique graph.
  • Bipartite representation preserves incidence exactly but expands the alignment problem from |V| to |V| + |E| nodes by adding one auxiliary node per hyperedge.
  • GW compares relational structures through a transport plan whose entries represent soft source-to-target matching support, then extracts a one-to-one correspondence by linear assignment.

IV. HYPERGRAPH ALIGNMENT FRAMEWORK

FALCON converts hypergraph structure into a sequence of node-level relational views and optimizes one shared GW transport plan so the resulting alignment remains consistent across scales.

  • FALCON keeps clique-based pairwise costs on the original nodes while avoiding a single collapsed clique representation.
  • At each filtration level, active hyperedges are converted into a clique-induced co-occurrence dissimilarity matrix, yielding a sequence of pairwise structural views.
  • A single shared GW transport plan aligns the views jointly rather than independently, requiring consistent explanations across hyperedge scales.
  • The optimized coupling is decoded into a discrete bijection by solving a linear assignment problem.

A. From Hyperedges to Filtration-Induced Costs

FALCON orders hyperedges by structural scores, synchronizes filtration levels, and converts active hyperedges into binary-overlap dissimilarity matrices that provide multi-scale node views.

  • From Hyperedges to Filtration-Induced Costs: FALCON assigns each hyperedge a degree-aware structural score based on the normalized total incident degree of its nodes.The score uses node hyperedge-degree values to order hyperedges from more peripheral toward more prominent regions.
  • From Hyperedges to Filtration-Induced Costs: Synchronized filtration buckets reduce weakly informative or one-sided refinements, with ξ controlling resolution: smaller values produce coarser representations and larger values retain more score variation.
  • From Hyperedges to Filtration-Induced Costs: Each filtration level activates a selected set of hyperedges, and cumulative or non-cumulative aggregation respectively combines evidence across scales or isolates score-range-specific signal.
  • From Hyperedges to Filtration-Induced Costs: The active hyperedges at every level are converted into clique-induced node dissimilarities, producing multi-scale structural views for source and target hypergraphs.
  • From Hyperedges to Filtration-Induced Costs: Binary-overlap dissimilarity treats nodes as close when they co-occur in at least one active hyperedge and ignores multiplicity changes that preserve co-occurrence.

B. Multi-Scale Optimal Transport

FALCON uses one shared transport plan to align filtration-induced structural views across scales. Its objective aggregates GW distortions across levels with entropic regularization.

  • The filtration produces multiple structural views, but FALCON requires one correspondence shared across all levels.A source-target node match should remain globally meaningful across filtration scales.
  • The shared coupling T belongs to the transport polytope defined by normalized node-degree marginals.Each marginal assigns mass according to node degree, measured by incident hyperedges.
  • At each filtration level, the GW distortion evaluates whether source pairwise relationships map to corresponding target relationships.The level-specific distortion compares structural distances under the same coupling.
  • The multi-scale objective aggregates distortions across filtration levels because no single level is privileged.An entropic regularizer is included in the joint objective.
  • Equation (5) is the central optimization objective of FALCON.

C. The FALCON Algorithm

FALCON optimizes the joint multi-scale GW objective with an entropic GW procedure, then decodes a discrete correspondence from the resulting transport plan. Its filtration levels are constructed algorithmically and weighted according to balanced edge evidence.

  • Optimization and decoding: The entropic GW solver linearizes the quadratic distortion and solves each transport subproblem with Sinkhorn scaling.The procedure starts from the product coupling and iterates outer updates.
  • Optimization and decoding: Each filtration level contributes a linearized cost matrix, and these costs are combined before the transport update.
  • Optimization and decoding: After convergence, the Hungarian algorithm solves a linear assignment problem on the optimized transport plan to produce the node mapping.
  • Algorithm pipeline: Algorithm 1 assigns filtration scores, builds synchronized buckets, constructs node marginals and active-edge sets, and forms dissimilarity matrices.
  • Algorithm pipeline: The algorithm solves the joint multi-scale GW objective to obtain the optimized coupling before decoding the mapping.
  • Level weighting: Balanced edge-count weighting assigns level weights from the amount of new hyperedge evidence contributed by both hypergraphs.A level receives high weight only when both sides contribute substantial new evidence.

D. Interpretation

FALCON interprets filtration levels as relational channels and preserves them with one shared coupling. This yields cross-scale structural alignment while retaining the original node set, although the induced pairwise views are lossy summaries of higher-order structure.

  • Cross-scale interpretation: The shared coupling supports a correspondence only when it preserves source-target relationships across the filtration.The objective therefore jointly explains the entire sequence of structural views rather than selecting one best level.
  • Relational-channel view: FALCON can be viewed as a filtration-induced vector-valued GW objective with one relational channel per filtration level.The channels are generated from hypergraph co-occurrence structure rather than observed attributes.
  • Consistency: Under relabeling-invariant construction, synchronized filtration buckets select corresponding levels in the two hypergraphs.
  • Scope boundary: The induced co-occurrence matrices are generally lossy, so distinct hypergraphs can produce identical views; the result is consistency with alignment, not an isomorphism test.
  • Aggregation choices: Cumulative aggregation reinforces accumulated co-occurrence evidence, whereas non-cumulative aggregation isolates score-range-specific signals.

E. Complexity

FALCON combines filtration preprocessing with a dense joint GW solver whose dominant cost scales cubically with the number of nodes. Memory scales quadratically in node count per filtration level.

  • Notation: Let n denote the node count, |E| the larger hyperedge count, ξ the number of buckets, and K the number of GW outer iterations.
  • Preprocessing: Sorting hyperedge scores costs O(|E| log |E|), while expanding hyperedges over contained node pairs costs O(Σe∈Ex |e|^2).
  • Optimization: The dense joint multi-scale GW solver costs O(ξKn^3), and the final O(n^3) assignment is dominated by this term.
  • Overall complexity: The total dense runtime combines score sorting, hyperedge expansion, and the joint GW term.
  • Memory: Space complexity is O(ξn^2) for scale-specific cost matrices plus dense quantities used by the shared GW solver.

V. EXPERIMENTS

The experiments evaluate FALCON on controlled perturbation benchmarks derived from real-world hypergraphs, comparing accuracy, robustness, ablations, and computational cost against graph- and hypergraph-alignment baselines.

  • The study asks whether FALCON remains accurate under increasing structural perturbation, benefits from multiple filtration views, and has acceptable computational cost.
  • Datasets: Experiments cover NDC, Email, House, and Dawn hypergraphs representing drug classes, email communications, congressional sponsorship groups, and drug-use episodes.
  • Benchmark construction: Benchmarks use incidence noise or subgraph sampling, followed by random node relabeling, to create paired hypergraphs with known ground-truth correspondences.Incidence noise flips matrix entries independently, whereas subgraph sampling retains each hyperedge with probability 1−p without changing retained hyperedge composition.
  • Evaluation protocol: Accuracy is measured as the fraction of correctly recovered node correspondences across five noise levels and 10 independent trials per level.Noise levels are p ∈ {0.05, 0.10, 0.15, 0.20, 0.25}; the target is randomly permuted, and the permutation provides ground truth.
  • Baselines: Baselines include graph aligners on clique and bipartite representations, BIGALIGN, TAME, and the native hypergraph method ELRUHNA.HyperAlign was excluded after reliable results could not be reproduced using the authors’ public implementation.
  • Reported outcomes: The reported results show robustness to structural perturbations and generally matching or outperforming strong graph- and hypergraph-alignment baselines.Tables report mean ± standard deviation over ten runs; OOT and OOM indicate out of time and out of memory.
  • FALCON configurations: FALCON is evaluated in cumulative and non-cumulative configurations using the same solver, hyperparameters, and filtration scoring.The default setup uses ξ = 32 buckets, β = 0.1, and entropic GW optimization with 200 outer and 10 inner iterations.

A. Results

FALCON is robust under structural perturbations, with multi-scale filtration generally outperforming single or collapsed representations and strong baselines. Its benefits are largest on larger, noisier hypergraphs, while bucket resolution and representation choices affect accuracy and runtime.

  • Accuracy and robustness: FALCON matches or outperforms all baselines on Email, House, and Dawn at every nonzero noise level, while degrading more gradually under perturbation.It remains competitive on NDC; several baselines either fail to complete on larger hypergraphs or approach random accuracy.
  • Accuracy and robustness: At p = 0.25 under incidence noise, FALCON retains about 82% accuracy on Email, exceeds 60% on House, and recovers 40.2% on Dawn.The corresponding baselines drop to 0.2% on Email for SGWL, below 2% on House for graph methods, and near zero on Dawn for nonhypergraph methods.
  • Accuracy and robustness: FALCON(nc) suits dense hypergraphs, whereas FALCON(c) suits sparse evidence or hyperedge removal because repeated co-occurrence across levels can compensate for missing observations.The preferred aggregation mode therefore depends on hypergraph density and the perturbation setting.
  • Multi-scale representation: Preserving multiple filtration-induced views and aligning them jointly is more robust than using any single or collapsed representation.Even an oracle single-bucket baseline is usually below FALCON variants, while pooled levels can fail when scale-specific evidence is destroyed.
  • Sensitivity and efficiency: Accuracy under incidence noise improves with finer filtrations and largely saturates around ξ ∈{16, 32}, whereas further refinement can hurt Email; ξ = 32 is a moderate default.Under subgraph sampling, accuracy is already high for small ξ and remains comparatively stable as buckets increase.
  • Ablations: The dissimilarity function has the largest ablation impact: Jaccard reduces Dawn accuracy from 55.3% to 23.6% and Email accuracy from 89.0% to 48.8% under incidence noise.Degree-aware filtration is especially important on Dawn, while balanced scale weighting usually differs from uniform weighting by at most 2–3 percentage points.

VI. CONCLUSION

FALCON is a fully unsupervised hypergraph-alignment framework that uses filtration-induced co-occurrence views and a shared multi-scale GW objective. Experiments show improved robustness to structural perturbations and competitive performance against strong baselines.

  • FALCON combines filtration-induced co-occurrence views with a shared multi-scale Gromov–Wasserstein objective.
  • One transport plan across filtration levels yields a globally consistent node correspondence while preserving structural evidence across scales.
  • Experiments showed improved robustness to structural perturbations.
  • FALCON performed competitively against strong graph- and hypergraph-alignment baselines.
Loading 2608.29635v1…