HODGE-AWARE CONTRASTIVE LEARNING

Let ${\mathcal{V}}=\{1,\ldots,N\}$ be a set of vertices. A $k-$simplex ${\mathcal{S}}^{k}$ is a subset of ${\mathcal{V}}$ that contains $k+1$ distinct elements. A simplicial complex ${\mathcal{X}}^{K}$ of order $K$ is a collection of simplices such that it contains at least one $K-$ simplex and if ${\mathcal{S}}^{k}\in{\mathcal{X}}^{K}$ we have that all subsets of ${\mathcal{S}}^{k}$ are also elements of ${\mathcal{X}}^{K}$. From a geometric representation perspective, in a SC of order $K=2$, nodes are $0$-simplices, edges are 1-simplices and (filled) triangles are 2-simplices [2, 3].

Neighborhood relations in an SC can be represented via the incidence matrices and Hodge Laplacians. Specifically, the incidence matrix $\mathbf{B}_{k}\in\mathbb{R}^{N_{k-1}\times N_{k}}$ captures the adjacencies between $(k-1)-$ and $k-$simplices. Consequently, $\mathbf{B}_{1}$ represents the node-to-edge incidence matrix and $\mathbf{B}_{2}$ the edge-to-triangle incidence matrix. For an SC of order two, ${\mathcal{X}}^{2}$, the related Hodge Laplacians are defined as:

$$\begin{array}[]{l}{{\mathbf{L}}_{0}}={{\mathbf{B}}_{1}}{\mathbf{B}}_{1}^{\top},\\ {{\mathbf{L}}_{1}}={{\mathbf{L}}_{1,\ell}}+{{\mathbf{L}}_{1,u}}:={\mathbf{B}}_{1}^{\top}{{\mathbf{B}}_{1}}+{{\mathbf{B}}_{2}}{\mathbf{B}}_{2}^{\top},\\ {{\mathbf{L}}_{2}}={\mathbf{B}}_{2}^{\top}{{\mathbf{B}}_{2}}\end{array}$$

(2)

where $\mathbf{L}_{0}$, $\mathbf{L}_{1}$, $\mathbf{L}_{2}$ represent the neighborhood relationships between nodes, edges, and triangles, respectively. Moreover, $\mathbf{L}_{0}$ coincides with the standard graph Laplacian [3]. The lower-Laplacian $\mathbf{L}_{1,\ell}=\mathbf{B}_{1}^{\top}\mathbf{B}_{1}$ and upper-Laplacian $\mathbf{L}_{1,u}=\mathbf{B}_{2}\mathbf{B}_{2}^{\top}$ split the edge adjacencies into relations that are due to common vertices and common triangles, respectively.

A $k-$simplicial signal $x^{k}$ is a mapping from a $k-$simplex to the set of real numbers that formalizes the simplicial data. We collect all $k-$ signals in vector ${\mathbf{x}}^{k}=[x^{k}_{1},\ldots,x^{k}_{N_{k}}]^{\top}$, where $x_{i}^{k}$ is the signal on the $i$th simplex and $N_{k}$ is the total number of $k-$simplices. For instance, we denote an edge flow as ${\mathbf{x}}^{1}=[x^{1}_{1},\ldots,x^{1}_{N_{1}}]^{\top}$ with $x^{1}_{e}$ being the flow on the edge $e=(m,n)$ in $\mathcal{S}^{1}$. In the sequel, we focus on edge flows to ease exposition and because of their wider applicability; thus we drop the superscript and denote them as ${\mathbf{x}}$.

SCs allow for a spectral processing of simplicial signals via the Hodge decomposition, which decomposes the space ${\mathbb{R}}^{N_{k}}$ as:

$${\mathbb{R}}^{N_{k}}=\text{im}({\mathbf{B}}_{k}^{\top})\oplus\text{im}({\mathbf{B}}_{k+1})\oplus\text{ker}({\mathbf{L}}_{k})$$

(1)

where $\text{im}(\cdot)$ and $\text{ker}(\cdot)$ are the image and kernels spaces of a matrix and $\oplus$ is the direct sum of vector spaces [4, 7]. Accordingly, we can decompose any edge flow ${\mathbf{x}}$, into three parts ${\mathbf{x}}={\mathbf{x}}_{\rm G}+{\mathbf{x}}_{\rm C}+{\mathbf{x}}_{\rm H}$ each living in an orthogonal subspace known as the gradient space ${\mathbf{x}}_{\rm G}\in\text{im}({\mathbf{B}}_{1}^{\top})$, the curl space ${\mathbf{x}}_{\rm C}\in\text{im}({\mathbf{B}}_{2})$, and the harmonic space ${\mathbf{x}}_{\rm H}\in\text{ker}({\mathbf{L}}_{1})$. In turn, the 1-Hodge Laplacian can be eigendecomposed as ${\mathbf{L}}_{1}={\mathbf{U}}\boldsymbol{\Lambda}{\mathbf{U}}^{\top}$ with eigenvectors ${\mathbf{U}}$ and eigenvalues $\boldsymbol{\Lambda}$. By grouping the eigenvectors as ${\mathbf{U}}=[{\mathbf{U}}_{\rm G},{\mathbf{U}}_{\rm C},{\mathbf{U}}_{\rm H}]$ and projecting the edge flow onto them gives rise to the embeddings $\tilde{\mathbf{x}}_{\mathrm{G}}=\mathbf{U}_{\mathrm{G}}^{\top}\mathbf{x}$, $\tilde{\mathbf{x}}_{\mathrm{C}}=\mathbf{U}_{\mathrm{C}}^{\top}\mathbf{x}$, $\tilde{\mathbf{x}}_{\mathrm{H}}=\mathbf{U}_{\mathrm{H}}^{\top}\mathbf{x}$. These embeddings encode different interpretable properties of the data, which we will exploit in Sec. 4 to design augmentations. Refer to [4] for more detail on the role of the Hodge decomposition on processing simplicial data.

Simplicial convolutional filters are linear parametric mappings that can process simplicial signals [7]. For an input edge flow ${\mathbf{x}}$, the filtered signal is ${\mathbf{y}}={\mathbf{H}}({\mathbf{L}}_{1}){\mathbf{x}}$ with simplicial filtering matrix:

$${\mathbf{H}}({\mathbf{L}}_{1}):=\bigg{(}\epsilon\mathbf{I}+\sum_{l_{1}=0}^{L_{1}}\alpha_{l_{1}}{\mathbf{L}}_{1,\ell}^{l_{1}}+\sum_{l_{2}=0}^{L_{2}}\beta_{l_{2}}{\mathbf{L}}_{1,u}^{l_{2}}\bigg{)}.$$

(2)

Here, $\{\epsilon,\alpha_{l_{1}},\beta_{l_{2}}\}$ are filter coefficients and $\mathbf{L}_{1,\ell}$, $\mathbf{L}_{1,u}$ propagate the edge signal via their respective neighbourhood relations. The filter is local in the sense that it moves information by at most $L=\max\{L_{1},L_{2}\}$ hops across the simplicial structure. Moreover, by exploiting the recursions ${\mathbf{L}}_{1,\ell}^{l_{1}}{\mathbf{x}}={\mathbf{L}}_{1,\ell}({\mathbf{L}}_{1,\ell}^{l_{1}-1}{\mathbf{x}})$, ${\mathbf{L}}_{1,u}^{l_{2}}{\mathbf{x}}^{k}={\mathbf{L}}_{ku}({\mathbf{L}}_{1,u}^{l_{2}-1}{\mathbf{x}})$ and since the Laplacian matrices are sparse, we can obtain the output with a cost of order ${\mathcal{O}}(LN_{1})$. The filter part related to the lower Laplacian acts on the signal gradient embedding, whereas that related to the upper Laplacian acts on the curl embedding. All the parameters contribute to processing the signal harmonic embedding. Refer to [7, Sec. IV] for the specific relation of filter (2) and decomposition (1).

The constant number of parameters and the linear computational complexity in the number of edges, make the filter (2) an appealing solution to learn representations from edge flows. To also learn non-linear mappings, simplicial convolutional neural networks (SCNNs) have been developed as layered structures interleaving filters with pointwise non-linearities [13]. Specifically, given the SCNN input ${\mathbf{x}}_{0}:={\mathbf{x}}$, the propagation rule at each layer $t$ is:

$$\mathbf{x}_{t}=\sigma\big{(}{\mathbf{H}}_{t}({\mathbf{L}}_{1}){\mathbf{x}}_{t-1}\big{)}$$

(3)

where $\sigma(\cdot)$ is a pointwise nonlinearity (e.g., ReLU). The final layer constitutes the SCNN output which provides its embedding. Compactly, we will denote the SCNN input-output relation as ${\mathbf{h}}:=f_{\mathcal{H}}({\mathbf{x}})$, where ${\mathbf{h}}$ is referred to as the SCNN embedding and set ${\mathcal{H}}:=\{\epsilon_{t},\{\alpha_{\ell_{1},t}\},\{\beta_{\ell_{2},t}\}\}_{t}$ collects the parameters of all layers. Furthermore, depending on the setting, a readout function is applied to ${\mathbf{h}}$ to transform it for the task at hand (e.g., binary classification).

Simplicial data often have particular properties in one of the three Hodge embeddings [3, 23], which may be wrongly affected by augmentations if ignored. Hence, following the InfoMin principle simplicial augmentations should destroy information on irrelevant Hodge embeddings and preserve it on the others. To account for the latter, we cast the dropout probabilities as a stochastic optimization problem, considering the expected value of the difference of the generated Hodge embeddings to the embeddings of the anchor. Specifically, consider the embeddings of an augmented example $\tilde{\mathbf{x}}^{\prime}_{\text{G}}=\mathbf{U}_{\mathrm{G}}^{\top}\mathbf{x}^{\prime}$, $\tilde{\mathbf{x}}^{\prime}_{\text{C}}=\mathbf{U}_{\mathrm{C}}^{\top}\mathbf{x}^{\prime}$, $\tilde{\mathbf{x}}^{\prime}_{\text{H}}=\mathbf{U}_{\mathrm{H}}^{\top}\mathbf{x}^{\prime}$. Then the expressions $\mathcal{L}_{\mathrm{G}}(\mathbf{p})=\mathbb{E}[\left\|\tilde{\mathbf{x}}_{\mathrm{G}}-\tilde{\mathbf{x}}^{\prime}_{\text{G}}\right\|_{2}^{2}]$, $\mathcal{L}_{\mathrm{C}}(\mathbf{p})=\mathbb{E}[\left\|\tilde{\mathbf{x}}_{\mathrm{C}}-\tilde{\mathbf{x}}^{\prime}_{\text{C}}\right\|_{2}^{2}]$, $\mathcal{L}_{\mathrm{H}}(\mathbf{p})=\mathbb{E}[\left\|\tilde{\mathbf{x}}_{\mathrm{H}}-\tilde{\mathbf{x}}^{\prime}_{\text{H}}\right\|_{2}^{2}]$ quantify the expected quadratic differences between the original and the augmented hodge embeddings. ¹¹1To see that these indeed depend on $\mathbf{p}$ use the equality $\mathrm{Tr}\left({\mathbf{X}}{\mathbf{X}}^{\top}\right)=\|{\mathbf{X}}\|_{2}^{2}$ and recall $\mathbb{E}\left[\mathbf{x}\circ\mathbf{e}\right]=\mathbf{x}\circ\mathbf{p}$. Then $\mathbb{E}[\left\|\tilde{\mathbf{x}}_{\mathrm{G}}-\tilde{\mathbf{x}}^{\prime}_{\text{G}}\right\|_{2}^{2}]=\left\|\tilde{\mathbf{x}}_{\text{G}}\right\|_{2}^{2}-\mathrm{Tr}\left(\mathbf{U}_{\mathrm{G}}\mathbf{x}(\mathbf{x}\circ\mathbf{p})^{\top}\mathbf{U}_{\mathrm{G}}^{\top}\right)-\mathrm{Tr}\left(\mathbf{U}_{\mathrm{G}}(\mathbf{x}\circ\mathbf{p})\mathbf{x}^{\top}\mathbf{U}_{\mathrm{G}}^{\top}\right)+\mathrm{Tr}\left(\mathbf{U}_{\mathrm{G}}\mathbf{P}\mathbf{U}_{\mathrm{G}}^{\top}\right)$, where $\mathbf{P}$ is a matrix with entries $\mathbf{P}_{i,j}=\mathbf{x}_{i}\mathbf{x}_{j}\mathbf{p}_{i}\mathbf{p}_{j}$ for $i\neq j$ and $\mathbf{P}_{i,j}=(\mathbf{x}_{i})^{2}\mathbf{p}_{i}$ for $i=j$. We use these distances to optimize the probabilities based on prior knowledge such that one or more of the augmented embeddings are similar while the remaining ones differ. For example, when the curl and harmonic embeddings are important, such as in the trajectory prediction task that we will touch in the experiments (Sec. 5), we could design ${\mathbf{p}}$ by solving:

	$\displaystyle\!\min_{\mathbf{p}}$		$\displaystyle-\mathcal{L}_{\mathrm{G}}(\mathbf{p})+\mathcal{L}_{\mathrm{C}}(\mathbf{p})+\mathcal{L}_{\mathrm{H}}(\mathbf{p})$		(5a)
	subject to		$\displaystyle\mathbf{p}\in\mathcal{G}_{\mathbf{p}}:=\left\{\mathbf{p}\mid\mathbf{p}\in[0,1]^{N_{1}},\|\mathbf{p}\|_{1}\leq\epsilon_{\mathbf{p}}\right\},$		(5b)

where set $\mathcal{G}_{\mathbf{p}}$ puts a maximum budget $\epsilon_{\mathbf{p}}$ on the allocated drop probabilities in a sparse manner (i.e., the $\ell_{1}-$norm $\|\cdot\|_{1}$ imposes sparse probabilities on a few flows). The budget $\epsilon_{\mathbf{p}}$ is tuned as a hyperparameter. ²²2In (5a), we could also weight the contributions of the different components (e.g., $\alpha_{\rm C}\mathcal{L}_{\mathrm{C}}(\mathbf{p})+\alpha_{\rm H}\mathcal{L}_{\mathrm{H}}(\mathbf{p})$ with scalars $\alpha_{\rm C},\alpha_{\rm H}>0$ when the signals have some contribution in each of them. By solving (5), we find the dropout probabilities $\mathbf{p}$ that generate examples with similar curl and harmonic components to the original data point but with a different gradient component. We solve this optimization problem with projected gradient descent, projecting $\mathbf{p}$ onto the constraint set ${\mathcal{G}}_{{\mathbf{p}}}$ after every step.

Problem (5) influences the embedding space by acting on the augmentation functions ${\mathcal{T}}_{1\backslash 2}(\cdot)$ to generate better positive examples. To further improve the organization of the embedding space, we shall also act on the negative samples. This is known as a debiasing technique and consists of reweighting the negative samples in the InfoNCE loss [24, 25, 26]. I.e., by optimizing w.r.t. the loss:

$$\mathcal{L}_{\text{weighted }}=-\sum_{\left(\mathbf{x}_{i}^{\prime},\mathbf{x}_{j}^{\prime}\right)\in{\mathcal{P}}}\log\left(\frac{e^{{\rm sim}\left(\mathbf{z}_{i}^{\prime},\mathbf{z}_{j}^{\prime}\right)/\tau}}{\sum_{m=1}^{M}w(\mathbf{x}_{i},\mathbf{x}_{m})\ e^{{\rm sim}\left(\mathbf{z}^{\prime}_{i},\mathbf{z}_{m}\right)/\tau}}\right)$$

(6)

where $w(\mathbf{x}_{i},\mathbf{x}_{m})$ is the weighting term between the anchor ${\mathbf{x}}_{i}$ and the negative example ${\mathbf{x}}_{m}$. For Hodge-aware learning, this weight should reflect the spectral properties of the data; thus, we would like to push spectrally different samples further away from the anchor.

We first consider a weighted embedding similarity between two data points:

$\displaystyle\begin{split}\mathcal{S}(\tilde{\mathbf{x}}_{i},\tilde{\mathbf{x}}_{m})=\gamma_{\rm H}\ \mathrm{CD}&(\tilde{\mathbf{x}}_{\mathrm{H},i},\tilde{\mathbf{x}}_{\mathrm{H},m})+\gamma_{\rm G}\ \mathrm{CD}(\tilde{\mathbf{x}}_{\mathrm{G},i},\tilde{\mathbf{x}}_{\mathrm{G},m})\\ &+\gamma_{\rm C}\ \mathrm{CD}(\tilde{\mathbf{x}}_{\mathrm{C},i},\tilde{\mathbf{x}}_{\mathrm{C},m})\end{split}$

(7)

$\mathrm{CD}(\tilde{\mathbf{x}}_{i},\tilde{\mathbf{x}}_{m})=1-\frac{\tilde{\mathbf{x}}^{\top}_{i}\tilde{\mathbf{x}}_{m}}{\left\|\tilde{\mathbf{x}}_{i}\right\|_{2}\left\|\tilde{\mathbf{x}}_{m}\right\|_{2}}$ is the cosine distance and weights $\gamma_{\rm H},\gamma_{\rm G},\gamma_{\rm C}\geq 0$ are picked based on prior knowledge about the task or tuned as hyperparameters. Choosing the cosine distance leads to higher negative values for spectrally more dissimilar examples. Then, we compute the weight as the normalized similarity over the $M$ negative samples:

$$w(\mathbf{x}_{i},\mathbf{x}_{m})=\frac{\mathcal{S}(\tilde{\mathbf{x}}_{i},\tilde{\mathbf{x}}_{m})}{\sum_{m=1}^{M}\mathcal{S}(\tilde{\mathbf{x}}_{i},\tilde{\mathbf{x}}_{m})}$$

(8)

which means that the weights for each datum sum to one and ensures that the loss terms for different data points are comparable. Summarizing the above, substituting (7) into (8) and the latter into (6) leads to an overall contrastive loss that pushes spectrally different samples away from the anchor based on this dissimilarity score. This encourages an embedding space that is organized with respect to the Hodge decomposition.