thgsp.bga

Harary

harary(A: torch_sparse.tensor.SparseTensor, vtx_color: Optional[Union[torch.Tensor, int, float, complex, str, bytes, numpy.generic, Sequence[Union[int, float, complex, str, bytes, numpy.generic]], Sequence[Sequence[Any]], numpy.typing._array_like._SupportsArray, List[int], Tuple[int]]] = None, threshold: float = 0.97) → Tuple[List[scipy.sparse.lil.lil_matrix], numpy.ndarray, numpy.ndarray, numpy.ndarray, Dict[int, int]][source]

Harary bipartite decomposition

Parameters

  • A (SparseTensor) – The adjacency matrix

  • vtx_color (array_like, optional) – All valid type for np.asarray() is acceptable, including torch.Tensor on cpu. If None, this function will invoke thgsp.alg.dsatur() silently.

  • threshold (float, optional) –

Returns

  • bptG (List[lil_matrix]) – An array consisting of M bipartite subgraphs formatted as scipy.sparse.lil_matrix

  • beta (array) – beta[:,i] is the bipartite set indicator of i-th subgraph

  • beta_dist (array) – A table showing the relationship between beta and channels

  • new_vtx_color (array) – The node colors

  • mapper (dict) – Map new_vtx_color to the original ones. For example mapper={1:2, 2:3, 3:1} map 1,2 and 3-th color to 2,3 and 1, respectively.

OSGLM

osglm(A: torch_sparse.tensor.SparseTensor, lc: Optional[int] = None, vtx_color: Optional[Union[torch.Tensor, int, float, complex, str, bytes, numpy.generic, Sequence[Union[int, float, complex, str, bytes, numpy.generic]], Sequence[Sequence[Any]], numpy.typing._array_like._SupportsArray, List[int], Tuple[int]]] = None)[source]

The oversampled bipartite graph approximation method proposed in 1

Parameters

  • A (SparseTensor) – The adjacent matrix of graph.

  • lc (int) – The ordinal of color marking the boundary such that all nodes with a smaller color ordinal are grouped into the low-pass channel while those with a larger color ordinal are in the high-pass channel.

  • vtx_color (iter) – The graph coloring result

Returns

  • bptG (lil_matrix) – The oversampled graph(with additional nodes)

  • beta (np.ndarray)

  • append_nodes (np.ndarray) – The indices of those appended nodes

  • vtx_color (np.ndarray) – The node colors

References

1

Akie Sakiyama, et al, “Oversampled Graph Laplacian Matrix for Graph Filter Banks”, IEEE trans on SP, 2016.

ADMM-based

admm_bga(A: torch.Tensor, M: int = 1, alpha: float = 100.0, metric: str = 'fro21', cut_edge: bool = True, B0: Optional[torch.Tensor] = None, convergence_marker: float = 1e-08, check_step: int = 1000, verbose: bool = False, nonnegative: bool = True, rho: float = 0.01, eta: float = 1.01, max_iter: int = 100000, early_stop: bool = False, max_rho: float = 10000000000.0) → torch.Tensor[source]

The program is to find the bipartite graph approximation via solving the following optimization problem 2 .

\[\begin{split}\begin{array}{ll} \min _{\left\{\mathbf{B}_{i}\right\}} & \sum_{i=1}^{L}\left\|\mathbf{ A}-\mathbf{B}_{i}\right\|_{F}^{2}+\alpha \sum_{i=1}^{L} \sum_{j \neq i} \operatorname{Tr}\left\{\mathbf{B}_{i}^{T} \mathbf{B}_{j}\right\} \\ \text { s.t. } & \mathbf{B}_{i} \in \mathcal{B} \end{array}\end{split}\]

Note

This algorithm does NOT guarantee bipartite output graphs in some cases. Nevertheless, the output graphs are almost bipartite,i.e., only a few edges violate the bipartiteness. One can use is_bipartite_fix() to fix the output under such circumstances.

Parameters

  • A (Tensor(N x N)) – N is the number of graph nodes

  • M (int, optional) – The number of bipartite graphs to learn

  • alpha (float,optional) – The parameter which controls the orthogonality among learnt bipartite graphs

  • metric (str,optional) – The error metric between the learned bipartite graphs and the original graph

  • cut_edge (bool,optional) – If True, cut the edges in the learned bipartite graphs that not exist in the original graph

  • B0 (Tensor,optional) – The initialization of B

  • convergence_marker (float,optional) – the procedure converges if the error between B and A < this value

  • check_step (int,optional) – the step interval to display iteration information

  • verbose (bool,optional) –

  • nonnegative (bool,optional) – If True, allow negative edge weight in the learned bipartite graphs B

  • rho (float,optional) – A step argument

  • eta (float,optional) – The update factor of rho

  • max_iter (int,optional) – The max ADMM iteration times

  • early_stop (bool,optional) – If True, the procedure will return B once all learned graphs are bipartite

  • max_rho (float,optional) –

Returns

B – The learnt bipartite subgraph(s)

Return type

Tensor(M,N,N)

References

2

Aimin Jiang, et al, “Admm-based Bipartite Graph Approximation”, ICASSP, 2019.

MFS

amfs(A: torch_sparse.tensor.SparseTensor, Sigma=None, level=None, delta=0.1, thresh_kld=1e-06, priority=True, verbose=False) → Tuple[List[scipy.sparse.lil.lil_matrix], numpy.ndarray][source]

AMFS bipartite approximation for graph wavelet signal processing 3.

Parameters

  • A (SparseTensor) – The adjacency matrix.

  • Sigma (scipy.spmatrix, optional) – The covariance matrix specified by the Laplacian matrix L. If None, \(\Sigma^{-1}=L+\delta I\)

  • level (int, optional) – The number of bipartite subgraphs, i.e., the decomposition level. If None, \(level=\lceil log_2( \mathcal{X}) \rceil\), where \(\mathcal{X}\) is the chromatic number of A.

  • delta (float, optional) – \(1/\delta\) is interpreted as the variance of the DC compnent. Refer to 4 for more details.

  • thresh_kld (float, optional) – Threshold of Kullback-Leibler divergence to perform AMFS decomposition.

  • priority (bool,optional) – If True, KLD holds priority.

  • verbose (bool,optional) –

Returns

  • bptG (List[SparseTensor]) – The bipartite subgraphs.

  • beta (Tensor(N, M)) – The indicator of bipartite sets

References

3

Jing Zen, et al, “Bipartite Subgraph Decomposition for Critically Sampledwavelet Filterbanks on Arbitrary Graphs,” IEEE trans on SP, 2016.

4

A. Gadde, et al, “A probablistic interpretation of sampling theory of graph signals”. ICASSP, 2015.

Greedy

bga Utils

beta2channel_mask(beta)[source]

Generate a (2^M, N) bool mask tensor to indicate which channel(color group) one node belongs to. All channels have disjoint node sets and hence the sum along the channel dimension returns a all-one(True) (N,) tensor.

Note

This function is a common approach to generate channel mask for multi-channel wavelet filterbank. Either coloring or numerical based bipartite approximation algorithm can employ this function.

Parameters

beta (BoolTensor(N,M)) – Bipartite partition indicator tensor. N and M are the node and bipartite subgraph numbers, respectively.

Returns

  • mask (BoolTensor(2**M,N)) – The indices of True in i-th row are nodes whose signal will be kept in i-th channel.

  • beta_dist (array(2**M,M))) – An array, see the doc of thgsp.filters.QmfCore for the details.

beta2color_group(beta, th=True)[source]

Actually, beta2channel_group is more exact since “color” here is not exact graph coloring. However we can take it as an approximation of graph coloring.

Parameters

  • beta (BoolTensor(N,M)) – Bipartite partition indicator tensor. N and M are the node and bipartite subgraph numbers, respectively.

  • th (bool, optional) – If True, the value of returned dict is Tensor otherwise array.

Returns

  • color_group (dict) – color_group[i] is a LongTensor (or array) of node indices colored with i-th color.

  • beta_dist (array) – An array, see the doc of thgsp.filters.QmfCore for the details.

beta_dist2channel_name(beta_dist, reverse=False)[source]

Generate the channel names(\(L\) or H) for each channel according to beta_dist. By default, 0 and 1 means H and L, respectively.

Parameters

  • beta_dist (ByteTensor(2^M,M)) – An array, see the doc of thgsp.filters.Qmf for the details.

  • reverse (bool,optional) – If True, 0 means L.

Returns

An array composed by H and L. Each row corresponds to one channel.

Return type

array

bipartite_mask(bt, sparse=True)[source]

Generate a bool mask matrix which can extract a bipartite subgraph from any graph (represented by a matrix) .

Parameters

  • bt (BoolTensor, array) – The indicator of two bipartite sets. All nodes within a same bipartite set is characterized by a same bool value, e.g.,True. Shape: (N,), N is the number of graph nodes.

  • sparse (bool) – If True, return lil_matrix.

Returns

Return type

lil_matrix,

cohere_color_idx(colors, color_group)[source]
Parameters

  • colors (Iterable) – Indices(ordinals) of colors. np.array([0,2,1]) means the 0,2,1-th color

  • color_group (dict) – color_group[i] is a np.ndarray of node indices colored with i-th color.

Returns

A Composed by node ordinals which are colored by any one among the colors.

Return type

LongTensor

is_bipartite_fix_th(A: torch.Tensor, fix_flag: bool = False) → Tuple[bool, List[int], torch.Tensor][source]

Check if a graph is bipartite using BFS-based 2-color coloring and furthermore can fix a graph to a bipartite one by deleting edges bridging two nodes colored with a same color.

Parameters

  • A (Tensor) – The adjacency matrix

  • fix_flag (bool,optional) – If True, fix A to a bipartite graph by zeroing some elements in-place.

Returns

  • flag (bool) – If True, the returned adjacency matrix represents a bipartite graph

  • vxt_color (list) – A list recording the vertex colors which are all 1 or 0.

  • A (Tensor) – The adjacency matrix of returned graph.