Algorithms

All algorithms take a GraphPair and return an instance with an align() method that produces a similarity matrix often referred to as P.

The similarity matrix is an n * n float array where P[i, j] scores how likely source node i maps to target node j. This matrix is doubly stochastic.

To turn P into a concrete node-to-node alignment and score it, pass the pair and P to the evaluation functions. They resolve the optimal assignment internally (via the Hungarian algorithm on -P) so you do not have to extract it by hand:

from libam import evaluation
score = evaluation.accuracy(pair, P)

Note that this is not built for scale, just for demonstrating how evaluation can be done.

Algorithms fall into two groups. Unrestricted algorithms align the graphs from structure (and optional features) alone. Restricted algorithms additionally use node data in order to align nodes with more detailed information.

Each factory below takes a GraphPair and returns an algorithm instance whose align() method produces P.

Unrestricted

libam.algorithms.fugal(pair: GraphPair, iterations: int = 1, simple: bool = True, mu: float = 0.05, efn: int = 3, **kwargs: Any) → Fugal

Feature-fortified Unrestricted Graph Alignment.

Parameters:

• pair – Graph Pair object

• iterations – Number of iterations for the alignment

• simple – Whether to use simple feature extraction

• mu – Regularisation parameter

• efn – Edge feature number (default 5 = standard FUGAL)

libam.algorithms.grampa(pair: GraphPair, eta: float = 0.2, **kwargs: Any) → Grampa

GRAMPA

Parameters:

• pair – Graph Pair object

• eta – Regularisation parameter

libam.algorithms.grampa_s(pair: GraphPair, eta: float = 0.2, init_sim: int = 1, eig_type: int = 0, **kwargs: Any) → GrampaS

GRAMPA-S

Parameters:

• pair – Graph Pair object

• eta – Regularisation parameter

• init_sim – Initial similarity type

• eig_type – Eigenvalue type

libam.algorithms.cone(pair: GraphPair, dim: int = 128, window: int = 10, negative: float = 1.0, niter_init: int = 10, reg_init: float = 1.0, lr: float = 1.0, bsz: int = 10, nepoch: int = 5, niter_align: int = 10, reg_align: float = 0.05, embsim: str = 'euclidean', numtop: int = 10, **kwargs: Any) → Cone

CONE (Consistent Network Alignment with Proximity-Preserving Node Embedding)

Parameters:

• pair – Graph Pair object

• dim – Embedding dimension

• window – Context window size

• negative

• niter_init

• reg_init

• lr – Learning rate

• bsz – Batch size

• nepoch – Number of epochs

• niter_align

• reg_align

• embsim – Embedding similarity metric

• numtop – Number of top candidates

libam.algorithms.gwl(pair: GraphPair, epochs: int = 1, batch_size: int = 64, use_cuda: bool = False, strategy: str = 'hard', beta: float = 0.1, outer_iteration: int = 20, inner_iteration: int = 10, sgd_iteration: int = 200, display: bool = False, prefix: str = '', prior: bool = False, dimension: int = 64, loss_type: str = 'L2', cost_type: str = 'cosine', ot_method: str = 'proximal', lr: float = 0.01, gamma: float = 0.5, max_cpu: int = 0, **kwargs: Any) → GWL

GWL (Gromov-Wasserstein Learning)

Parameters:

• pair – Graph Pair object

• epochs – Training epochs

• batch_size – Batch size

• use_cuda – Use CUDA if available

• strategy – Sampling strategy, ‘hard’ or ‘soft’

• beta

• outer_iteration

• inner_iteration

• sgd_iteration

• display – Print training progress

• prefix

• prior

• dimension

• loss_type

• cost_type – Cost metric type

• ot_method – Optimal transport solver method

• lr – Learning rate

• gamma

• max_cpu – Max CPU threads - 0 for unlimited

libam.algorithms.sgwl(pair: GraphPair, mn: int, loss_type: str = 'L2', ot_method: str = 'proximal', beta: float = 0.2, iter_bound: float = 1e-10, inner_iteration: int = 2, sk_bound: float = 1e-30, node_prior: float = 1000, max_iter: int = 4, cost_bound: float = 1e-26, update_p: bool = False, lr: float = 0, alpha: float = 1, clus: int = 2, level: int = 3, **kwargs: Any) → SGWL

SGWL (Scalable Gromov-Wasserstein Learning)

Parameters:

• pair – Graph Pair object

• mn

• loss_type

• ot_method

• beta

• iter_bound

• inner_iteration

• sk_bound

• node_prior

• max_iter

• cost_bound

• update_p

• lr

• alpha

• clus

• level

libam.algorithms.path(pair: GraphPair, **kwargs: Any) → Path

Path

Parameters:

pair – Graph Pair object

libam.algorithms.isorank(pair: GraphPair, L: object = None, lalpha: float = 1.0, weighted: bool = True, alpha: float = 0.5, tol: float = 1e-12, maxiter: int = 1, **kwargs: Any) → Isorank

IsoRank

Parameters:

• pair – Graph Pair object

• L – Pre-computed similarity matrix (default None, computed from lalpha)

• lalpha – Degree-based similarity scaling factor (default 1.0)

• weighted – Whether to use weighted similarity (default True)

• alpha – Teleportation probability (default 0.5)

• tol – Convergence tolerance (default 1e-12)

• maxiter – Maximum iterations (default 1)

libam.algorithms.nsd(pair: GraphPair, alpha: float = 0.5, iters: int = 5, **kwargs: Any) → NSD

NSD (Network Similarity Decomposition)

Parameters:

• pair – Graph Pair object

• alpha – Damping factor (default 0.5)

• iters – Number of iterations (default 5)

libam.algorithms.mmnc(pair: GraphPair, train_ratio: float = 0.04, k_de: int = 3, k_nei: int = 7, t: int = 10, fast_select: bool = False, **kwargs: Any) → Mmnc

MMNC (Multi-order Matched Neighborhood Consistent Graph Alignment in a Union Vector Space)

Parameters:

• pair

• train_ratio

• k_de

• k_nei

• t

• fast_select

• kwargs

Returns:

libam.algorithms.dspp(pair, **kwargs) → DSPP

DSPP (DS++)

Parameters:

pair – Graph Pair object

libam.algorithms.fgot(pair: GraphPair, tau: int = 1, n_samples: int = 5, epochs: int = 1000, lr: int = 1, std_init: int = 5, loss_type: str = 'w_simple', seed: int = 42, verbose: bool = True, tol: float = 1e-12, adapt_lr: bool = False, **kwargs)

FGOT (Graph Distances Based on Filters and Optimal Transport)

Parameters:

• pair

• tau

• n_samples

• epochs

• lr

• std_init

• loss_type

• seed

• verbose

• tol

• adapt_lr

Returns:

libam.algorithms.got(pair: GraphPair, it: int = 20, n_samples: int = 20, epochs: int = 10, lr: float = 0.1, alpha: float = 0.1, ones: bool = True, loss_type: str = 'w', seed: int = 42, verbose: bool = False, **kwargs)

GOT (An Optimal Transport framework for Graph comparison)

Parameters:

• pair – Graph Pair object

• it

• n_samples

• epochs

• lr

• alpha

• ones

• loss_type

• seed

• verbose

libam.algorithms.grasp(pair: GraphPair, n_eig: int = 100, q: int = 20, k: int = 20, laa: int = 3, icp: bool = True, icp_its: int = 3, lower_t: float = 0.1, upper_t: float = 50, linsteps: bool = True, base_align: bool = True, **kwargs) → Grasp

GRASP (Scalable Graph Alignment by Spectral Corresponding Functions)

Parameters:

• pair

• n_eig

• q

• k

• laa

• icp

• icp_its

• lower_t

• upper_t

• linsteps

• base_align

• kwargs

Returns:

libam.algorithms.klaus(pair: GraphPair, a: int = 1, b: int = 1, gamma: float = 0.4, stepm: int = 25, rtype: int = 1, maxiter: int = 1000, verbose: bool = False, **kwargs) → Klaus

KLAUS

Parameters:

• pair

• a

• b

• gamma

• stepm

• rtype

• maxiter

• verbose

• kwargs

Returns:

libam.algorithms.lera(pair: GraphPair, iters: int = 30, method: str = 'lowrank_svd_union', b_match: int = 1, default_params: bool = True, **kwargs) → Lrea

LERA (Low Rank Spectral Network Alignment)

Parameters:

• pair

• iters

• method

• b_match

• default_params

• kwargs

Returns:

libam.algorithms.mds(pair: GraphPair, n_components: int = 10, alpha: float = 0.05, max_iter: int = 600, eps: float = 0.01, tol: float = 0.001, min_eps: float = 0.001, eps_annealing: bool = True, alpha_annealing: bool = True, gw_init: bool = True, return_stress: bool = False, **kwargs) → Mds

MDS (Unsupervised Manifold Alignment with Joint Multidimensional Scaling)

Parameters:

• pair

• n_components

• alpha

• max_iter

• eps

• tol

• min_eps

• eps_annealing

• alpha_annealing

• gw_init

• return_stress

• kwargs

Returns:

libam.algorithms.net_align(pair: GraphPair, a: int = 1, b: int = 1, gamma: float = 0.5, dtype: int = 0, maxiter: int = 100, **kwargs) → NetAlign

Net-Align

Parameters:

• pair

• a

• b

• gamma

• dtype

• maxiter

• kwargs

Returns:

libam.algorithms.parrot(pair: GraphPair, sep_rwr_iter: int = 100, prod_rwr_iter: int = 20, alpha: float = 0.5, beta: float = 0.15, gamma: float = 0.5, in_iter: int = 50, out_iter: int = 20, l1: float = 0.1, l2: float = 0.1, l3: float = 0.1, l4: float = 0.01, **kwargs) → Parrot

PARROT (Position-Aware Regularized Optimal Transport for Network Alignment)

Parameters:

• pair

• sep_rwr_iter

• prod_rwr_iter

• alpha

• beta

• gamma

• in_iter

• out_iter

• l1

• l2

• l3

• l4

• kwargs

Returns:

libam.algorithms.regal(pair: GraphPair, attributes: str | None = None, numtop: int = 10, alpha: float = 0.01, buckets: float = 2, k: int = 10, gammastruc: float = 1.0, gammaattr: float = 1.0, untillayer: int = 2, **kwargs) → Regal

REGAL (Representation Learning-based Graph Alignment)

Parameters:

• pair – Graph Pair object

• attributes – Path to a saved numpy matrix of node attributes (None for structural only)

• numtop – Number of top similarities to keep via KD-tree (0 = all pairwise)

• alpha – Discount factor for further layers

• buckets – Base of log for degree binning (1 = no log binning)

• k – Controls the number of landmarks to sample (d = k*log(n))

• gammastruc – Weight on structural similarity

• gammaattr – Weight on attribute similarity

• untillayer – Calculate xNetMF until this layer (0 = no limit)

Restricted

libam.algorithms.gradp(pair: GraphPair, anchor_links: list | None = None, **kwargs: Any) → GradP

GradP (Grad-Align+)

Parameters:

• pair – Graph Pair object

• anchor_links – Lost of anchor pairs in src and target graphs (optional)

libam.algorithms.joena(pair: GraphPair, anchor_links: ndarray, hidden_dim: int = 128, out_dim: int = 128, alpha: float = 0.9, gamma_p: float = 0.01, in_iter: int = 5, out_iter: int = 10, init_threshold_lambda: float = 1.0, lr: float = 0.001, epochs: int = 30, runs: int = 1, device: str = 'cpu', **kwargs) → Joena

JOENA (Joint Optimal Transport and Embedding for Network Alignment)

Parameters:

• pair

• anchor_links

• hidden_dim

• out_dim

• alpha

• gamma_p

• in_iter

• out_iter

• init_threshold_lambda

• lr

• epochs

• runs

• device

Returns:

libam.algorithms.htc(pair: GraphPair, src_laps: Tensor | None = None, trg_laps: Tensor | None = None, hid_dim: int = 500, num_utrn: int = 15, ulr: float = 0.01, num_ftune: int = 25, flr: float = 0.01, alpha: float = 1.1, k: int = 40, p: float = 0.5, graphlet_size: int = 4, **kwargs) → HTC

HTC (Towards Higher-order Topological Consistency for Unsupervised Network Alignment)

Parameters:

• pair – Graph Pair object

• src_laps – Precomputed source graphlet-orbit built from pair.src when None.

• trg_laps – Precomputed target graphlet-orbit built from pair.tar when None.

• hid_dim

• num_utrn

• ulr

• num_ftune

• flr

• alpha

• k

• p

• graphlet_size

libam.algorithms.slot_a(pair: GraphPair, step_size: float = 0.1, bases: int = 2, joint_epoch: int = 100, epoch: int = 100, gw_beta: float = 0.01, **kwargs)

SlotA

Parameters:

• pair

• step_size

• bases

• joint_epoch

• epoch

• gw_beta

Returns:

libam.algorithms.alpine(pair: GraphPair, anchor_links: List[Tuple[int, int]] | None = None, k: int | None = None, connected: bool = False, mu: float | None = None, niter: int = 10, sinkhorn_iters: int = 500, sinkhorn_tol: float = 1e-09, method: Literal['FW', 'AMD'] = 'FW', **kwargs) → Alpine

Parameters:

• pair

• anchor_links

• k

• connected

• mu

• niter

• sinkhorn_iters

• sinkhorn_tol

• method

Returns:

Base Class

class libam.algorithms.algorithm.AlignAlgorithm(pair: GraphPair)

Abstract base class for all graph alignment algorithms.