A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learning
Authors: Amadou Siaka SANGARE
Nicolas Dunou
Jhony H. Giraldo
Fragkiskos D. Malliaros
Venue: Accepted by TMLR ()

Abstract: Self-supervised learning has become a key method for training deep learning models when labeled data is scarce or unavailable. While graph machine learning holds great promise across various domains, the design of effective pretext tasks for self-supervised graph representation learning remains challenging. Contrastive learning, a popular approach in graph self-supervised learning, leverages positive and negative pairs to compute a contrastive loss function. However, current graph contrastive learning methods often struggle to fully use structural patterns and node similarities. To address these issues, we present a new method called Fused Gromov-Wasserstein Subgraph Contrastive Learning (FOSSIL). Our method integrates node-level and subgraph-level contrastive learning, seamlessly combining a standard node-level contrastive loss with the Fused Gromov-Wasserstein distance. This combination helps our method capture both node features and graph structure together. Importantly, our approach works well with both homophilic and heterophilic graphs and can dynamically create views for generating positive and negative pairs. Through extensive experiments on benchmark graph datasets, we show that FOSSIL outperforms or achieves competitive performance compared to current state-of-the-art methods.

Published in Transactions on Machine Learning Research (03/2025)
A Fused Gromov-Wasserstein Approach to Subgraph Con- trastive Learning
Amadou S. Sangare
LTCI, Télécom Paris Institut Polytechnique de Poris, France
Nicolas Dunou
nicolas. nitoosa..drruu@@mmmeeeessttteeee
Éoole des Mones de Suint-Eliennr
Université Paris Douphine-PShe Pronce
Jhony H. Giraldo
jhony.giraldon pocooooddde.oooooo............a.
LTCI, Télcom Poris Instifut Polytechnique de Paris, France
Fragkiskos D. Malliaros
Université Paris-Saclay
CentruleSupétee, Inria, France
Reviewed on OpenReview: https: // openrevie.. net/ form? id= J7cY9JJJ99
Abstract
Self-supervise learning has become a key method for training deep learning models when labeled data is scarce or unavailable. While graph machine learning holds great promise across various domains, the design of effective pretext tasks for self-supervised graph repre- sentation learning remains challenging. Contrastive learning, popular approach in graph self-supervised learning, leverages positive and negative pairs to compute contrastive loss function. However, current graph contrastive learning methods often struggle to fully use structural patterns and node similaritics. To address these issues, we present new method called Fused Gromov Wasserstein Subgraph Contrastive Learning (FOSSIL). Our model in- tegrates node-level and subgraph-level contrastive learning, seamlessly combining a standard node-level contrastive loss with the Fused Gromov-Wasserste distance. This combination helps our method capture both node features and graph structure together. Importantly, our approach works well with both homophilic and heterophilic graphs and can dynamically create views for generating positive and negative pairs. Through extensive experiments on benchmark graph datascts, we show that FOSSIL outperforms or achieves competitive performance compared to current slate-offthe-arl methods.
1 Introduction
Self-Supervised Learning (SSL) is methodology employed in machine learning to extract meaningful and transferable representations from unlabeled data. SSL has been successfully used in many areas, like puter vision (Tomasev et al. 2022). speech processing (Bacvski et al., 2020), and natural language processing DDvlin et al. 2019 Lewis et al. 2019). SSL is particularly important when labeled data is impractical or costly to obtain. Graph Representation Learning (GRL) stands out as a domain where SSL excels due to the complexity involved in annotating graphs, which often demands specialized knowledge and cannot be easily crordds For instance, in biochemistry (Zang al. (203),, annotating molecular graphs requires specialized knowledge, significantly increasing the labeling effort compared to other data modalities.

---

Published in Transactions on Machine Learning Research (03/2025)
In SSL, Contrastive Learning (CL) is prominent approach (Chen et al. involve sampling an anchor from the dataset, generating an augmentation (positive pair), and contrasting it with negative pairs using a CL loss function. Unlike certain modalities, such as images, the generation of positive pairs in GRL presents unique challenges. Various methods have been proposed, inchuding those
2020b CL methods typically
involving node-level or subgraph-level contrastive loss functions (Zhu et al.; 2020b Yuan et al.] 2023 Han
ct al.
2022: Jiao et al.] 2020). Recent studies have shown that subgraph-level approaches outperform node- ones, as they can capture the structural similarities between the anchor and positive graph pair (Han
level
et al.
2022
Prior subgraph-level CL methods often use readout functions to extract subgraph representations (Jiao et al. 2020: Veličković et al. 2019). Alternatively, some approaches rely on Optimal Transport (OT) distances for computing the CL loss (Han et al., 2022). OT-based techniques exhibit superior performance compared to readout-based methods in subgraph-leve CL. Notably, the Generative Subgraph Contrast. (GSC) method (Han et al.] 2022) leverages a combination of the well-established Wasscrstein Distance (WD) (Villani et al., 2009) and Gromov-Wassersiee methodologies face two challenges: separately computing the WD and GWD does not capture both structural and feature information simultancously when comparing subgraphs, and the Graph Neural Network (GNN) encoder struggles with heterophilic datasets.
Distance (GWD) (Mémoli 2011] from OT. However, existing OT-based
Motivated by the limitations of previous subgraph CL methodologies, we introduce a new GCL approach employing the Fused Cromov-Wasserstell Distance (FGWD) (Vayer et al.] 2018 Brogat-Motte et al. 2022) from OT. The FGWD captures both feature and structural similarities jointly. Our model, termed Fused Gromov Wasserstein Subgraph Contrastive Learning (FOSSIL., is designed to be robust against variations in homophily levels within the graph dataset. The proposed method uses a decoupled scheme to process heterophilic data more effectively. Furthermore, FOSSIL leverages the FGWD to simultaneously encode the structural and feature characteristics of our subgraphs for calculating the CL loss. We conduct a com- prehensive comparative analysis of FOSSIL against statc-of-tho-art models across various homophilic and heterophilic datasets for self-supervised node classification tasks. Our findings demonstrate that FOSSIL ei- ther outperforms existing methodologies or achieves competitive results, thereby showcasing its efficacy in graph SSL tasks. The main contributions of our paper can be summarized as follows:
We introduce a novel approach, named FOSSIL, that effectively captures both feature and structural similarities simultaneously with the FGWD, addressing the limitations of previous OT-based SSL meth- ods in GRL.
We design a robust architecture capable of accommodating varying levels of homophily within graph datasets. By using a decoupled scheme for the GNN encoder, FOSSIL performs consistently well across homophilic and heterophilic datasets. This robustness enhances the applicability of the proposed method in real-world scenarios.
We conduct an extensive empirical evaluation to validate the effectiveness of FOSSIL against statc-of- the-art models in self-supervised node classification lasks across diverse datasels. We also thoroughly validate each design choice of FOSSIL through a series of ablation studies.
2 Related Work
2.1 Graph Neural Networks
GNNs are neural architectures designed for graphs (Wu et al. 2021). They usually extract information via message-passing mechanisms between nodes. This process be divided into two steps: message aggrega- tion from the neighborhood and updating of the node embedding (Gilmer et al. 2017). The key difference between state-of-the-art GNN architect ures lies in the aggregation functions. For example, Graph Convo- lutional Networks (GCNs) Kipf & Welling 2017) perform a weighted average of the messages inside the 1-hop neighborhood, where weights are fixed and defined with respect to the node degrees. Graph Attention Networks (GATs) (Veličković et al. 2018) compute learnable attention weights thanks to interactions inside the 1-hop neighborhood. Nevertheless, most of the GNN architectures are built. under the homophily as-
2

---

Published in Transactions on Machine Learning Research (03/2025)
sumption. This assumption is useful in graph datasets where nodes have similar characteristics. Therefore, these GNNs have poor node classification performance in heterophilic graph datasets.
Previous research works have tried to address the heterophilic limitation of classical message- message-passing neural networks. For example, GPR-GNN (Chien et al. 2021) uses a polynomial graph filter with coefficients learned altogether with the linear projection layer used GNNs. H2GCN (Zhu et al. 2020a) proposes a set of designs to improve the node classification performance of GNN on heterophilic graphs: feature-structure embedding separation, aggregating in higher-order neighborhoods, and combination of intermediate representations (which is equivalent to adding skip connections between GNN layers). From a graph signal processing perspective (Isufi ct al. 2024). GCNs are considered low-pass filters (NT & Machara, 2019). Therefore, ACM (Luan et al. 2022) adaptively combines information extracted by a graph low-pass filter, a high-pass filter, and an MLP to address heterophilic networks.
In FOSSIL we adopt a decoupled encoder design similar to ACM (Luan et al. 2022,, making our encoder agnostic to the input graph's 's level of homophily. Specifically, we use a GNN with a normalized adjacency matrix without self-loops and the identity, which implements a vanilla message-passee passing function and an MLP. These two representations are then adaptively combined with fusion module. The message-passing module of our GNN is equivalent to the low-pass channel of ACM, while the MLP is the identity channel. Intuitively, we make our encoder more robust, to different levels of homophily with the two representations.
2.2 Self-supervised Learning on Graphs
The key idea of SSL on graphs is to design and solve some pretext tasks that do not require label information. Depending on how the pretext task is defined, SSL methods for graphs can be divided into two categories: predictive and contrastive methods. Predictive methods aim learn meaningful representations where the output is typically a perturbed version of the input graph. For example, BGRL (Thakoor et al. 2021 learns node representations by encoding two perturbed versions of the input graph with an online encoder and target encoder. The online encoder is trained to predict the represcntation of the target encoder, and the target encoder is updated as an exponential moving average of the online encoder. BNLL (Liu el al. 2024) improves the BGRL model by introducing a few noisy-ground truth positive node pairs. Based on the homophily assumption that neighboring nodes often share the same label, they include additional candidate positive pairs to the objective of BGRL. Specifically, for each node, BNLL adds the cosine similarity of its online representation and the target representations of its neighbors weighted by its attention weights with its neighbors. VGAE (Kipf & Welling) 2016) uses variational autoencoder approach in graphs to predict the same graph and feature as in the input. Finally, GPT-GNN (uu et al. 2020b) performs an autoregressive reconstruction of the graph.
Contrastive methods, which are also the focus of this paper, have shown better performance than predictive methods for SSL on graphs in general. Such methods can be divided into three categories depending on how the data pairs are defined: node-to-node, (Zhu et al., 2020b) generates two perturbed views of the original graph and performs contrastive lcarning between the nodes of these views. MUSE (Yuan et al. 2023 extracts node-wise semantic, contextual, and fused embeddings to perform node-to-node contrastive learning for each of these embeddings. Nevertheless, node-level contrastive learning approaches are suboptimal since they cannot easily capture global information about the structure of the graphs
taap-,, and node-to-graph. For example, GRACE
Regarding subgraph level contrast, DGI (Veličković et al. 2019) performs -ode-to-graph contrast by extract- ing the node embeddings of the original graph and perturbed version, then it increases or decreases the agreement between the original or perturbed node embeddings using readout function. Though spectral polynomial filters such as GPR-GNN (Chien et al.) 2021 and ChebNetll (He et al. 2022) are more expressive than GCNs and can adapt to arbitrary homophily levels, they underperform GCNs when used as an encoder for traditional SSL methods. PolyGCL (Chen et. al.] 2024) tries to solve this problem by restricting the expressiveness of the polynomial filters from a spectral perspective to construct the low-pass and high-pass views and introduces a simple linear combination strategy to construct the optimization objective. Specif- ically, they follow a similar approach to DGI (Veličković et al. (2019) with the difference that they do it with both high/low- fowffreyyy embeddings extracted with high-pass and low-pass, polynomial filters sharing
3

---

Published in Transactions on Machine Learning Research (03/2025)
weights. Subg-Con Con (Jiao et al. 2020: follows up the work of DGI by doing the same contrast but at sub- graph level. It starts by sampling set of anchor nodes, followed by the extraction of subgraphs utilizing the personalized PageRank algorithm. Overall, the model aims to adjust the agreement level between an anchor node and the sampled subgraph for the positive and negative pairs. Methods such as DGI and Subg-Con, however, use a readout embedding to characterize graphs, which ignores the structure of the graph. GSC (Han et al. 2022) addresses this issue by performing subgraph-level contrast using WD and GWD from OT as the measure of subgraph similarity.
FOSSIL is combined subgraph-level and node-level contrastive learning approach. Our model uses OT distance metrics to measure the dissimilarity between subgraphs while further incorporating node-level con- trast to capture differences among nodes. While sharing common features, our method differs from GSC in three key aspects: (i) we jointly capture structural and feature information in the OT distance using the FGWD, (ii) we perform node-level contrast to emphasize the node's difference, and (iii) we have specialized architecture that is robust both homophilic and heterophilic datasets.
3 Preliminaries
3.1
Mathematical Notation
In this paper, matrices are represented with uppercase bold letters like A, while lowercase bold letters like x denote vectors. The symbol (;,-) denotes the matrix scalar product associated with the Frobenius norm. For an element x of a measured space, óg represents the Dirac measure al x. The vector 1, E R." denotes the vector of all ones of dimension n. We denote the simplex histogram with bins as Σ, {h E R. En h, = 13. Let L be a 4-way tensor and B be a matrix. The tensor-matrix multiplication between L and B is denoted as the matrix L @ B, where (L & B) = EE1 L...A..BBB. Be, The element-wist (Hadamard) product operator between two matrices is of vectors and V.
denoted as @. The fraction denotes the element-wise division
3.2 Graph Neural Networks
We consider nodo-attributed and undirocted graphs, denoted as 9 (A.X), where A N represents the adjaceney matrix, X NxF denotes the feature matrix, and N and F respectively denote the number of nodes and the dimensionality of each node feature vector. A GNN is function f RNN x Nxr + NNND where H = f(A, X) E N represents the node embeddings matrix of G, with each row H; corresponding to the embedding of node (Wu et al. 2021p. Additionally, for a vector v E RN, diag(v) E RN* denotes the diagonal matrix with diagonal elements from v. Let S S (1,..., N} be a set of indices; A[S; represents the adjacency matrix of the subgraph of & restricted to nodes indexed by S, and X[S] denotes its corresponding feature matrix.
3.3 Fused Cromov-Wasserster Distance
The main purpose of OT is to find the optimal way to shift objects from one location to another in metric space. This is done by finding a minimum cost soft matching between two probability distributions, one on objects of each location. Let μ E En and v E En be two probability distributions, respectively, over the objects of the first and the second location. The WD (Villani et al. 2009) uses matrix M E Raxm of transportation costs (or pair-wise distances) between location and 2 to find a soft matching that minimizes the overall transportation cost. However, locations 1 and 2 may not lie in the same space, preventing from defining the transportation cost M. GWD (Mémoli) 2011) solves this problem by using internal transportation cost matrices C₁ and C2 in each space separately to find the soft matching. The purpose is to match objects that have similar structural behaviors inside their metric spaces.
The main downside of WD and GWD that they fail to capture both structural and feature information (Vaeer et al., 2018) when used to compare graphs. fact, WD only uses node features to define cost matrix M, while GWD only uses each graph's adjacency matrix to define its internal costs matrices C₁ and Cz. To alleviate this issue, Vayer et al. (2018) proposed the Fused Gromov- Gromov- Wasserstein Distance (FGWD).
4

---

Published in Transactions on Machine Learning Research (03/2025)
The idea is to use coefficient [0, that trades off between WD and GWD. The FGWD between the two locations is defined as follows:
min (aM+ + ([C,, C2) PPP)) FGWD,.MC,,c,(H..) P)ll(..)
(1)
where PE Ru is soft matching (or joint probability distribution) between objects of location 1 and 2, I C2). = [i C2 and [p, v) is the set of joint probability distributions with marginals H and v. FGWD is a generalization of WD and GWD. We recover WD for a = 1 and GWD for = 0.
3.4 Graph Contrastive Learning (GCL)
GCL You et al. 2020 Xie et al. 2021 is built upon the Mutual Information Maximization principle (MIM) [innker 1988).
Given a graph G sampled from a graph distribution Pg, the goal is to learn an encoder f()) by maximizing the mutual information between 9 and its encoded version f()). The encoder f should be able to distinguish different graphs. Hence, we solve:
max MI(G:f(()) where ~ Fg..
(2)
For computational efficiency, in practice, maximize estimated lower bound MI of the mutual infor- mation. These lower bounds are used to maximize the similarity between positive pairs and minimize the similarity between negative ones. Formally, given graph g ~ Pg, and a graph view generation operator TG)) that creates different but semantically similar versions t(g) of G, the problem writes:
max MI(S( (((G))) where ~ F& and ((g) T()).
In this work, we use the Jensen- -hasnnnn estimator (Nowozin 2016 for our subgraph- contrastive learning and the InfoNCE (van den Oord et al. 2018) for node-level contrastive learning.
The learned representation f(G) can then be transferred to graph-level or node-level downstream task by plugging in carefully designed decoder:
min dowwustream (
(4)
where V, Dec(-), Ode, and Ldownstream are respectively the labels, the decoder (or prediction head), the parameters, and the loss for the downstream task.
4
Fused Gromov-Wasserstein Subgraph Contrastive Learning (FOSSIL)
4.1
Overview
Figure [ illustrates the pipeline of our proposed method, referred as FOSSIL. FOSSIL comprises five primary stages: (i) encoding, (ii) view generation, (iii) fusion layer, (iv) subgraph sampling, and (v) SSL loss computation based OT for subgraph-level plus node-level contrastive loss. FOSSIL takes input graph G and employs two neural nelworks with shared weights as encoders. The first neural network performs linear projection, while the second implements GNN (Kipf & Welling 2017). both equipped with the same Iearnable parameters W. Subscquently, view generation follows a docoupled stratogy similar to the encoder, utilizing a GAT (Veličković et al.) 2018). The fusion layer combines the outputs from the encoder and generator using a linear combination. Finally, subgraphs are sampled the encoder and generator levels compute the subgraph-level CL loss using the FGWD as the distance metric, and node-level contrastive loss is additionally computed.
4.2 Encoder
Several GNNs for sulf-supervised node classification are built under the homophily assumption, meaning that they assume the nodes in the neighborhood share similar labels (Han et al. 2022). As a consequence,
5

---

Published in Transactions on Machine Learning Research (03/2025)
Input Graph
Encoder
Generator
Fusion
Sampling
f [I, X)
g(l, IT')
H
A
H
ENC.
GAT
h(H/ H
Shared Weights
Sbared Weights
SSL. Loss
H
H
H
ENC.
GAT
A(H At*)))
((, X)
9 A, IT))
Figure Pipeline of FOSSIL for self-supervised node classification tasks. The proposed method integrates encoding, view generation, fusion, subgraph sampling, and CL in attributed graphs. FOSSIL employs shared-weit weight encoder and generator with GNNs to extract informative representations, subsequently fused for enhanced learning. Subgraph sampling facilitates subgraph-level CL loss computation based on the FGWD.
they typically perform badly when evaluated on heterophilic graph datasets. Several works (huu et al. 2020a; Hamilton et al., 2017 Defferrard et al. 2016 Abu-El-Haija et al. 2019 Chien et al. 2021 proposed new architectures to tackle this issuc in the supervised domain. Surprisingly, these more powerful encoders underperform a simple GCN in current GCL methods (Chen et al. 2024)). Based on these observation and following (Zhu et al. 2020a),, we propose a decoupled encoding, where we use GNN and an MLP with shared weights W RFDD Nodes are encoded as follows:
= (IXW) + diiag()) H¹ diag(A)H?)
(5)
where o()) is non-lincarit, I is the identity matrix, = D A/2 1/2 is the normalized adjacency matrix, D = diag(Al w) E NN is the diagonal matrix of node degrees and À E [0, 1] a vector that dictates how the two terms are combined. We explain how to compute À more detail in Sec. 4.4
In (5) we adaptively combine an MLP embodding, termed fcature embedding, and a GNN embedding, termed structural embedding. Self-lopps not considered in the adjacency matrix, so the GNN only aggregates information from its neighbors. Intuitively, the decoupling strategy proves effective due to the presence of two distinct sources of information in an attributed graph: node features and graph structure. The relevance of each information source can vary depending on the downstream task at hand. For instance, in the context of a social nerwork, individual user features often play a primary role in defining users, while friendship connections offer supplementary insights into their interactions. Conversely, in a citation network, it could more crucial to examine the documents cited by an article to predict its category effectively. homophilic graphs, traditional GNN encoding typically outperforms MLPs, whereas on heterophilic graphs, MLPs tend to perform better (Zhu et al.) 2020a). The decoupled approach enables us to better adapt the SSL model to the homophily level of the graph.
essence, on
4.3 Generator
Generating positive pairs in SSL for graphs is still open problem of research. A common approach here involves perturbing the original graph to preserve the underlying semantics (You et al. 2020 Qiu et al., 2020). However, determining these perturbations for graphs is not straightforward. State-of-the-arr methods usually apply hand-crafted pert urbations like random node fealure masking and random edge dropping, Such perturbations lack control and can degrade the intrinsic properties the original graph hence increasing the risk of false positives (Wang al., (202)). Moreover, the performance of these hand-crafted perturbations heavily depends on the characteristies of the particular graph dataset. Therefore, an additional step is required to manually identify the appropriate perturbation method tailored to each dataset.

---

Published in Transactions on Machine Learning Research (03/2025)
In FOSSIL, we adopt an end-to-end perturbation strategy, meaning that we learn the correct perturbation from the data. We use a similar strategy as in the encoder to separately generate node feature perturbations and graph structure perturbations. Given the feature embeddings H and structure embeddings H* from the encoder, we generate perturbations as A = g H A = ((,HH) where g RNNN x RNF + RND corresponds to GAT model (Veličković et al. 2018 Intuitively, we leverage the allention weights of the GAT to adaptively generate perturbations. At the feature level, this is equivalent to applying adaptive scaling to the node features, while at the graph structure level, this is equivalent to adaptively dropping some edges.
4.4 Fusion Layer
We combine the feature and structure information from the encoder and generator to obtain the final node embeddings. To this end, we apply adaptive node-wise fusion layers with shared weights 0. This stems from the fact that nodes do not necessarily require the same amount of structural information. At the encoder level, for each node 2/ we combine the semantic and structural information as follows:
A; (HH H (A1 v)60) 0),
(6)
H.
H. + A.H,
(7)
where sb RD RD x + RR is an MLP (with sigmoid the last activation function) computing how much structural information each node needs, and À E [0, 1] is the vector of the fusion coefficients of the graph nodes. Similarly, for the generator, we have the following:
Å (ff fr. (A1n) v).) A h MH H At! + +
(8)
(9)
Following (Yuan et al. 2023 we incorporate the degrees the nodes Aln into the fusion module. The rationale behind this choice is to leverage the node degree centralities account for the connoctivity infor- mation of each node inside the graph. Therefore, we help function (-)) in computing the fusion coefficients X that are more sensitive to the structure of the graph.
4.5 Subgraph Sampling
Using the original node embeddings H and the perturbed node embeddings Á, we sample the subgraphs that will be subsequently used contrastive samples. To this end, first sample without replacement set of anchor-node indices S C (1,...,N} From each anchor node e S, sample a set of node indices S; of size k (including v4) using breadth-first sampling in the 2-hop neighborhood of v; If we do not get the required size k; then the subgraph is not included in the subgraph-level contrast. Therefore, we create two subgraphs using each S,. The first subgraph is given by G = (A[S; H(S.)). The second subgraph is 6J. 6, given by 0:- (A[S; St], (((S)),, where A., s(h,, h,y) lb. 1 21a These subgraphs are used in our CL loss function using the FGWD. A perturbed subgraph corresponds to the original subgraph contextualized by the GAT we are using for adaptive graph perturbation. The intuition is that this contextualized subgraph further captures the sinilarities between nodes inside the original subgraph, hence, it should be similar to the original subgraph while adding additional context information to the nodes. In this work, for simplicity, we choose to randomly sample subgraphs. Some studies have proposed more adaptive and data-driven subgraph sampling techniques, which present an interesting direction for future work in subgraph contrastive learning (Niepert et al. 2021 Bevilacqua et al. 2024 Kong et al., 2023). This subgraph sampling approach breaks the cquivariance of our encoder with respect to the contrastive loss. However, this does not negatively impact the performance of FOSSIL in the datasets we use (please see Sec. 5
4.6 Self-supervised Loss Function
The SSL loss function in FOSSIL is given by two terms: a contrastive loss Coontrast and regularization term Lo to guide the learning of the fusion layer. The contrastive loss is at the same time divided into
7

---

Published in Transactions on Machine Learning Research (03/2025)
OT loss Lot and node-level contrastive loss Luodes that Ccontrast Lot + Lnode- Our final loss is thus given by L = Lcontrast + La-
4.6.1 OT distance-based subgraph-level contrastive loss Lot
In FOSSIL, we consider graphs as measured spaces by endowing them with probability distributions over their nodes. The probability mass given node represents the node's relative importance in the graph. With no prior knowledge of the graphs, we assume uniform probability distribution over its nodes.
Let G = (A1, Hi) and G2 = (Ag, H3) be two subgraphs. We measure the difference between Of and Øj using the FGWD as follows:
Digw gi (2) FGWD c*(,),
(10)
where μ is the uniform distribution over nodes of Gi is the uniform distribution on the nodes of 9 C
exp(-Ai/7), C² = exp(-A3/7) and C ex HH (H)) /T) is the matrix of pairwise transportation costs between their nodes (the exponentials on matrices are applied element-wise). We use FGWD to jointly exploit both features and structure information inside the two graphs to compute their distances. In this work, we solve the optinization problem associated with FGWD using the Bregman Alternated Projected Gradient (BAPG) method (Li al. 2023 given in Alg. App. A Our subgraph-level contrastive loss can be thus written
log (((exp(-Digu 91)/T))
ot
(M +
EES
(11)
M
log (1 - (exp(( (app(-Di (0,09,")) (;,,,,,))T)))
j=1
where S' is the set of sampled anchor-node indices defined in Sec. 4.5 G is a sampled subgraph, and g.n, is its j-th negative view used in the contrastive loss. For each node, we define M negative views in [11 h. In practice, we set M = 2 and define g.nh = Gj and G: = G3 with j randomly picked in {j E S j * i}. In the contrastive loss Lue, Lalign aims to incrcase the agrcement between posítive pairs while freg aims decrease the agreement between negative pairs.
4.6.2 Node-level contrastive loss Lnode
We also incorporate node-level contrastive loss. This improves our downstream node classification perfor- mance, as demonstrated later in our experiments. The node-level loss writes:
exp(s(h;, fT./7) Ejer (x) + Σÿ exp(s(h,, f2z)/))
1(h, h.) - log
(12)
N
Guode
Σ 1=1
((h, + (()
(13)
2N
One may notice that 12 presents a memory bottleneck coming from the contrastive loss at the node level N matrix for the pairwise cosine similarities between all pairs
Cuode- This loss requires the storage of of nodes within the graph, hence O(N2) of memory complexity. This limits the scalability of FOSSIL to large-scale graphs. To avoid this issue, propose FOSSILv2 model that considers only the union of nodes within the sampled subgraphs when computing the contrastive loss at the node level. Hence, the alternative node-level contrastive loss becomes:
Lnode-v2
Σ
(Ibb, ho), 1(hi, h.))
(14)
USES S3
iEU, S
With this expression, we have a memory complexity of (((S))))D) which scales constantly with respect N for FOSSIT.v2.
8

---

Published in Transactions on Machine Learning Research (03/2025)
4.6.3 Embedding fusion loss Lg
The embedding fusion loss guides the fusion layer learning behavior. The main motivation for this loss is to prevent the structure and leature embeddings from the encoder from being too similar. To this end, when the structure and feature embedding are very similar, we assume that we should emphasize more the feature promote low values in the vector X for the concerned nodes. We also couple the Co and the OT loss through the parameler a. Notice that 1 a in the definition of the FGWD in ① represents the relative weight of structure similarity when comparing subgraphs with OT. Therefore, we promote the values of À to align with 1- a on average so that À aligns with the OT distances. Additionally, we constrain the variance of À with L2 regularization to put more control on the way we combine embeddings. Our fusion layer loss function thus given as:
embedding. Thercfore,
N Σ (1-
Cg Σ h. B:ll +
(15)
where $1 and 32 are regularization parameters.
4.7
Computational Complexity of the Framework
4.7.1
Time complexity
Here, we analyze the computational complexity of our subgraph-level contrastive loss in 10 To compute FGWD, we use the BAPG method described in Alg. [ of App. A which is a single-loop method for solving the non-convex quadratic optimization problem of FGWD. The tensor product L(C,, C2) can be computed with complexity Onn'm + +nm?). So the gradients computed lines and of Alg. can be computed with complexity O(n2m m nm²). The other operations of Alg. [ have complexity ((mm)- Hence, the time complexity of BAPG is O[T(nmm + nm²)) overall, where and are, respectively, the order of the first and second graph, and T is the number of iterations that have been performed. Now we need to compute the cost. matrices M, C1, and C2 that are inputs of the BAPG algorithm. Those are computed with an overall complexity OnmDD, where D is the dimension of the embedding vectors. Finally solving the optimization problem in (1) with Alg. 1 has complexity (TT(pmm + nm²) + nmD).
At each iteration of our method, we sample |S] sub- graphs, each with & nodes (so k). Then, for each subgraph, we compute its FWGDs with its positive view and its M nega- tive views, which costs O(M + 1) + D2D)) in time. Hence, solving all the optimization problems costs (M + 1)(? + D)D)) in time. Finally, we need compute the contrastive loss with the FGWDs, which is done in O(IS)(M 1)). Overall the time com- plexity of computing (M 1)(3 + 1s2 D)).
Time per iteration
in the case where
10P
OT loss
Node- lovel-level loss
Others
Time (s
10
10
0
10,000
20,000
30,000
It is worth noting that this time complexity only de- pends on the hyperparameters of our method. In par- ticular, the cubic term 13 is not a real concern in prac- tice, as chosen such that & N, with N the num- ber of nodes in the graph. Therefore, the complexity of computing fot does not have scalability issues with the size of the input graph as it remains constant w.r.t. N.
Number of nodes N
Figure 2: Time per itcration of the different compo-
nents of FOSSIL in GPU A40 48G.
In our framework, we also compute node-level contrastive loss Lnode- This loss is computed with complexity O(N2D) theoretically. However, in practice, as computing the pair-wise cosine similarities between nodes inside the graph is parallelized thanks to matrix multiplication on the GPU, the complexity is roughly constant depending on the number cores and memory available on the GPU.
To experimentally validate this thcoretical analysis, we evaluate the time required for computing each loss with synthetic graphs generated with the contextual stochastic block model (cSBM) (Chien et al. 2021

---

Published in Transactions on Machine Learning Research (03/2025)
Table 1: Statistics of the datasets used in this work.
Cora
CiteSeer
PubMed CoAuthor-CS
Actor
Chameleon
Squirrel
(G)
0.81
0.74
0.80
0.81
0.22
0.24
0.22
Nodes
708
3, 327
19,717
18, 333
7, 7,600
2, 277
5,201
Edges
10, 556
9, 104
88, 648
163, 788
30, 019
36, 101
217,073
Features
1, 433
3, 703
500
805
932
2,325
2,
Classes
7
6
15
5
5
We vary the number of nodes N from 1,000 30, 000, and for each value of N, we measure the times on 5 synthetic graphs with arbitrary homophily levels. We fix k 12, D 512, |S] 300, and M 2 for this experiment. Fig. 2 shows that the time required to compute the OT loss and node-level contrastive losses remains roughly constant. for any value of N. Overall, in Fig. 2 we observe that our method scales reasonably well with the size of the graph. The empirical time complexity depicted by the green bars does not siguificantly increase from a graph with 1, 000 nodes to one with 30, 000 nodes.
4.7.2 Memory complexity
Computing the FGWD with Alg. requires storing all the cost matrices and the intermediate matrices used inside the algorithm. Hence, this entails a memory complexity of O(n2 + m² + nm) for two graphs of order n and m. In our case, n = m = k, and we compute the FGWD of all the S 11 subgraph pairs together inside the same batch. Therefore, we have memory complexity of O S + 1)) for fot- The memory complexity of the optimal transport component of FOSSIL is thus constant w.r.t. the size of the graph N.
5 Experimental Framework and Results
We perform a set of experiments to compare our model with several approaches in the literature. We compare FOSSIL with nine state-of- thett-rrtrrrttt methods inchuding: GSC (Han et al. (002). DGI (Veličković et al.] 2019).
DSSL (iaoo et al.) 2022). BGRL Thakoor et al., (021), GRACE (Zhu et al. 2020b), MUSE (Yuan et al. 2023), Subg-Con (Jiao et al. 2020 PolyGCL (Chen et al. 2024h. and BNLL (Liu et al. 2024 In addition. we compare FOSSIL with GSC using as the encoder the Chebyshev graph convolution (Deferrard et al. 2016) (GSC+Cheb) instead of the regular GCN to make the GSC framework more robust to heterophilic datasets. We evaluate all methods in four homophilic datasets Cora (McCallum et al.) 2000), CiteSeer (Snn et al. 2008). PubMed (Namata et al. 2012). and CoAuthor-CS (Shchur et al.] 2018);; and in three heterophilic dalasets Actor (Tang et al.] 2009),, Chameleon, and Squirrel (Rozemberczki et al. 2001]) We perform additional experiments in large-scale datasets in App. [ Table [Soles]sssss the statistics of the datasets tested in this work, where H (G) is the homophily of the graph as defined in (Pei ct al. 2020 Finally, we also run a set of ablation studies to analyze different aspects of FOSSIL.
We use standard downstream logistic regression accuracy with the self-supervised node embeddings to evaluate all compared moth We split the data into a development set (80%) and a test set (20%) once, ensuring that the test set is not used during the hyperparameter optimization process. Therefore, we split the development set into training and validation sets for hyperparameter tuning. Following (Klicpera et al. 2019 Giraldo al.] 2023), we take 20 nodes per class for the training set and the rest into the validation set for Cora, CiteSeer, and PubMed. For the other datasets, the training set gets 60% of the nodes, and the validation set gets the other 40% in the development set. Finally, keeping the original test set. test seeds to randomly split the dataset into the train and validation, while We train and evaluate the encoder on those splits and report the average performances accompanied by 95% confidence intervals calculated by bootstrapping with 1, 000 samples. Unlike other works in SSL for graphs, we do not perform model selection during SSL training by looking at the downstream test/valll /ssaviliaaiion performance. Finally, we take the encoder at the end of the SSL training to extract the node embeddings for the downstream evaluation. All experiments are conducted on A40 48GB and P100 16GB GPUs.
test each method using 100
10

---

Published in Transactions on Machine Learning Research (03/2025)
Test accuracy on the node classification task for different baseline models and FOSSIL. The best results are highlightod in bold, while the second pest-performing methods are underlined.
Table 2:
Method
Cora
CiteSeer
PubMed
CoAuthor CS
Actor
Chameleon
Squirrel
FS-GCN
80.0440.26
69.05
a7.33
92.50+0.00
29.6940.11
45.4840.25
30.26
FS-MLPP
57.28
56.37+0.37
69. 69.20+0.43
92.05
30.08+0.20
48.6840.33
37.1420.16
GSC
79.29=0.20
54.56
76.98+0.50
90.1640.00
28.4342.116
42.90+0..0
28.98=0.22
GhC+Cheb
76.84.0.26
68. 19.111p 10.26
75.7540.45
89.20
32.46
43.99
35.03
MUSE
62.5
58.05.10.4
79.08 40.31
54.32 1.76
36.61 10.15
52. 52.11
=0.17
DGI
79.90
70.22
77 27.80
87.38 10000 0.08
29.11
36.21
29.58
DSSL
20.39
54.16 10.64
69.98
87. 87.7340000
26.60+0:14
48.38
34.9920.21
BGRL
62.95 20.87
38. 18.00211.6
72.93
91.81 91.81
27. 27.93
36.90
28.91
GRACE
80.86 0.29
60.86
79.84
93.01 20.03
28.91
43.87
30.60 30.60
Subg-Con
44.32.0002
30.07+0.91
67 67.35.40.85
82.29
27. 27.60+0.18
45.6040.44
37.16
PolyGCL
80.95.0.20
71.38
76.39
OOM
26.52+0.07
32.75 12.
34.25
BNLL
41.57
70.45.2.92
93.60
25.33+0031
50.18
36.63_0.50
FOSSIL
80.02
68.2440.31
79.76 +0.44
94.49 10.04
35.61 10.15
53.03 +0.33
37.13 0.
FOSSILv2
78.94
68. 1642.3
79.09#0.38
95.0440.08
35.41
53.14+1.24
31.79=0.21
5.1
Implementation Details
We implement all methods using PyTorch KKekkrr 2017 and PyG (Fey & Lenssen
Our encoder is two-layer GCN with hidden dimension 024 and output dimension 512, and PReLU (He et al. 2015) activation function between them. In all experiments, our method is trained for 300 epochs with the Adam (Kingma & Ba
2019
2015) optimizer. We optimize the other hyperparameters with the framework The search spaces for hyperparameters are defined as follows: 1) learning rate 10-
Optuna (Akiba et al. 2019).
Ir e (10-$,5x 10 10
3): 2) learning rate of fusion module by (10-4,5 10 10-4 10 10 10-3,10-223 3) a {10 0.1 I}}; 4) the FGWD regularizer
(10-3, 5 x 10-3, 100210-22200 2,5 x 10-2, 10-15,
10,1,,, 5) the number of nodes in each sampled subgraph & E [10,30] 6) the temperature parameter E {0.2, 0.5, 0.8, 1.0, 1.5, 2.0, 3.0); 7) the GNN dropout parameter E {0.1, 0.2, 0.3, 0.4), and 8) the fusion MLP dropout Ps E (0.1,0.2, 0.3, 0.4). The value of B₂ is fixed to 1. We tune the hyperparameters by performing 100 trials in the development set. Finally, for each trial, we sample the values from the search space using the Troe-structured Parzen estimator (Watanabe] 2023). We study the sensibility of some important hyperparameters of FOSSIL in App. C The source code of FOSSIL is publicly available
5.2 Results and Discussion
Table 2 shows the results of the comparison of FOSSIL against previous state-of-the-art models for self- supervised node classification. We evaluate all methods with our setting to have a fair comparison. Our encoder is a decoupled GCN without self-loops; thus, we also evaluate GCN in a fully supervised setting, which we refer to as FS-GCN. We also evaluate a fully-supervised MLP (FS-MLP) for reference.
In Table 2 we observe that FOSSIL out performmss FS-MLP and FS-GCN, suggesting that pre-trained models using self-supervision and then fine-tuned on downstream task outperform end-to-end supervised models. In general, FOSSIL ranks either as the best or second best method among the bascline models used across both homophilic and heterophilic datasets. We also observe that FOSSIL is better than MUSE and GRACE on average, showing that node-level only contrast is suboptimal compared to including subgraph- level contrast for node classification.
It is also important to highlight that FOSSIL outperforms DGI and tubg-Con, which use a readout function to characterize a graph. This suggests that a simple readout. function does not properly capture the structure of the graph. Besides, these methods perform node-grapp graph contrast. Maximizing the agreement of an anchor node and its sampled subgraph is not optimal for node classification since this subgraph can contain a
https://github. htttiaauu..ccmsaaaaegeeee com/ssangaran/OSSTT
11

---

Published in Transactions on Machine Learning Research (03/2025)
Table Impact of subgraph similarity metric node classification.
Cosim
WD
GWD
FGWD
Landa
Cora
CiteSeer
PubMed
CoAuthor CS
Actor
Chameleon
Squirrel
x
66.0420.51
61.322u.as
70.13
84.33
34.27 34.27
42. 22
33. 33.35gg.2
K
61.822n.44
59.06gn.30
71 01.94
21.22
35.64
4..20
23.09
X
60.73
50 50.88
68 28.5
20.98
33.57 11:45
52. 12.0
31.07:00.6
J
75.19
65.2210.m
77.5920-4
94.61 s0.0
35.7920.18
48, 48.9510.00
33.61g0.22
V
X
X
X
J
28.00
69. 69.14
78.58
94.80
35.11
56.42
35.66
X
X
X
78. 28.22
69.9510.2
71.56.0.38
91.16go.0
31.22ga.15
60.37 20u49
37.48 10:25
X
19.11
67.72
27.30
91.01 goot
34.29
30.511..955
35.25
V
80.02:0.26
68. 68.244n..4
79.76g0.4s
94.4920.04
45.61
53.03
37.13
majority of dissimilar nodes (particularly in heterophilic graphs) hence, its readout representation can false positive. This can be observed by the performance of DGI on hetcrophilic graphs.
FOSSIT, works better than the previous OT-based method GSC, showing that joint feature-structure subgraph similarity metric together with & decoupled embedding extraction benefits from the structural patlerns inside the graph. Therefore, FOSSIL induces more relevant perturbalions. Resulting in a more accurate contrastive training. Interestingly, FOSSILv2 has competitive performance in all compared datasets while being more scalable than many other methods of the literature. Therefore, FOSSILv2 offers a good compromise between performance and scalability. This suggests that our proposed model is a promising direction when scalability is a key factor.
5.3 Ablation Studies
We validate the effectiveness of cach component of FOSSIL through series of ablation studies. First, we validate the use of the FGWD that captures both feature and graph structure similarities between subgraphs. Notably, we retonstrate that adding the node-level rastive loss consistently improves our downst noss-clasiificatinn performance. Then, we validate the design of our encoder by testing other alternatives. We also explore other strategics to generate graph perturbations within our framework. Finally, we validato the usage of using node connectivily information for the fusion module vb()) to assist the computation of X.
5.3.1 Impact of the subgraph similarity metric
We replace the FGWD with other subgraph similarity metrics to evaluate its effectiveness. More precisely, we use other OT distances like WD and GWD. We also use a simple average pooling of the subgraphs' node features followed by a cosine similarity (referred to as Cosim). To properly assess the effect of every similarity function, we evaluate their performance with and without adding the node-level contrastive loss Grode- Table 3 shows the results of this ablation study in all datasets. We first notice that node features are more important than pure graph connectivity for the node classification tasks. Indeed, GWD, which relies solcly subgraph structure similarity, performs worse than WD and Cosim. Sccondly, observe that WD performs better than Cosim. This suggests that OT distances are belter for self-supervised learning in estimating graph similarities than a Readout function followed by a cosine similarity. Nevertheless, both WD and Cosim ignore the underlying graph structure. Interestingly, we observe the superior performance of using the FGWD that jointly captures the feature and structure similarities between subgraphs. This aligns with the observations of (Vayer et al. 2018). Finally, we notice that adding node-level castrastive loss consistently improves our node classification results.
5.3.2 Impact of encoder design
We analyze the effectiveness of our encoder by replacing it with vanilla GCN and GCNII (Cen et al, 2020a) architocture. As shown in Table 4 the decoupled approach outperforms the standard GCN on the heterophilic datasets. Moreover, GCNII also underperforms our simple encoder. This aligns with the observation of Chen et al. (2024) that encoders specifically designed to work on arbitrary homophily levels do not perform well on current GCL methods. We also note a significant improvement the performance of the homophilic datasets with the decoupled approach, emphasizing its importance in the FOSSIL framework.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Table 4: Ablation study on the encoder method.
Encoder
Cora
CitcSeer
PubMed CoAuthor CS
Actor
Chameleon
Squirrel
GCN
74.72 19
61.35
74. 74.11=0o0
90.12 06
13 30.54
48.68
25
GCNII
50,18 44
46.45
68. 68.59
88,17
36.10
44.7510.33
33.71
Decoupled encoder
80:02
68.24
79.76.0.48
94.4944..0
35.61
53.03
37.13
Table 5: Graph perturbation ablation study results on node classification.
Generator
Cora
CiteSeer
PubMed
CoAuthor CS
Actor
Chameleon
Squirrel
Random
78. 28.28
65.85
76. 76.5440.12
20.40
28.95+1.58
57.29
38, 38.22
GAT-F
20.17
66.8 66.85
70.2540.51
92.72
31.68
53.6940.30
20.53
F-GAT-E
25.53
62.72
78.33
90.60
33.68
52.68
33.82=0044
GCN-E
76.95
67.30
79.4440.50
43.4
34.333..02
46.83
39.43 20.23
GAT-E
80.02
68.24
79.76.2.48
94.49 10.04
35.61 10.15
53.03
37.13
Table 6: Ablation study on fusion the design of the fusion
Design
Cora
CiteSeer
PubMed
CoAuthor CS
Actor
Chameleon
Squirrel
w/o centrality
80.24
67 27.9
79.95
95.0420.04
35.76
54.24
36.43-0027
w/ degree
80.0210.2e 10.26
68.2410.34
79.76_a.44
94.4910.04
35.61
53.03 10.33
37. 37.1310.20
w/ degree normalized-1
79.44.0.20
68.77 10.27
79.36_a.d
94.78
30.48
53.00
36.791o.21
w/ degree uormalized-2
69.77
79.70_0.35
94.3920.05
35. 35.16
53.94
36.97=0.20
w/ pagerank
79. 00.50
69.633g..0
79.45-0.42
94.34+n.0s
35.9420.15
54.84=0.40
36.77=0.22
w/ cigenscore
29.45
19.8910.27
79.83_a.37
93.9012.08
36.08
53.6720.77
37.38_0.61
5.3.3 Impact of the view generation process
We validate the design of the generator of FOSSIL by testing other alternatives. We first replace the generator with a traditional parammeeet random perturbation scheme (denoted as Random). Specifically, we perform random edge dropping (~ 15%) to assess the benefit of a learnable view generation. Moreover, we investigate whether to apply the GAT on embeddings (GAT-E), initial features (GAT-F), or an intermediate approach in which we compute altention weights with the features and directly apply them on the embeddings (F-GAT-E). Finally, we replace the GAT with a GCN that is applied to the embeddings (GCN-E). Table 5 shows the results of this ablation study. First, notice that both the GCN and GAT models outperform the random perturbation. Even though random perturbation presents competitive results, it requires careful fine-tuning of the hyperparameters according to the graph YYou et al., 2020). Secondly, we notice that applying the GAT on initial features does not work well compared to applying it on the node embeddings. We believe that applying the GAT on node features in our framework is equivalent to learning a different encoder, which not aligned with the intended view generation. The intermediate approach (F-GAT-E) also yields competitive results but still underperforms (GAT-E), suggesting that this approach is less aligned with the intended view generation compared to (GAT-E). However, applying the GAT on node embeddings is more aligned with the initial intuition to generate similar views. Finally, we observe that GAT-E provides better results than GCN-F since the attention mechanism provides flexibility during contrastive learning.
5.3.4 Ablation on the design of the fusion module
We incorporate the degree information of nodes in our fusion module. Intuitively, this brings useful structural information on nodes inside the graph. To validate this intuition, we explore different alternatives. More preciscly, we remove the degree information and test other node centralities: scaling degrees with N (normalized-1) or by the sum of degrees (normalized--2), PageRank (Page el al., 1999) and Eigenvector Burr 1982) centralities. T shows the results of this study. We observe that removing the node degree outperforms the degree centrality in some datascts. Nevertheless, we further observe that other global centrality measures like Eigenscore or PageRank outperform the baseline in several cases. Therefore, the degree of centrality offers good trade-off between complexity and performance.
13

---

Published in Transactions on Machine Learning Research (03/2025)
6 Conclusion
In this paper, introduced novel subgraph-based contrastive learning framework utilizing the Fused -assor-asssr distance to measure subgraph similarities. Drawing inspiration from recent advance- ments in addressing heterophily with GNNs, we implemented a decoupled embedding extraction strategy, rendering our method agnostic to the graph's homophily level. This approach allowed us to independently generale feature and structure perturbations adaptively. Our exlensive experimental evaluation demon- strated that our method outperforms or has competitive performance against state-of-the-arr frameworks across multiple benchmark datasets with varying levels of homophily. Our findings also highlight the chal- lenges posed by heterophilic datasets. We suggest future research avenues, such as integrating a high-pass feature extractor to enhance performance in such scenarios. Similarly, extending FOSSIL to other down- stream tasks such as link prediction or graph classification deserves further research.
Acknowledgments
We thank the anonymous reviewers for their suggestions and feedback. This work supported in part by ANR (French National Research Agency) under the JCJC projects GraphlA (AN1=20-CE22-009400)) and DeSNAP (ANR-24-CFF33-1855-00)
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Ler- man, Greg Ver Steeg, and A. G. Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference Machine Learning, 2019.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohla, and Masanori Koyama. Optuna: A next- generation hyperparameter optimization framework. ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, 2019.
Alexci Baevski, Henry Zhou, Abdel rahman Mohamed, and Michael Auli. wav2vec 2.0: A framework for self-supervised learning of speech representations. In Advances in Newral Information Processing Systems, 2020.
Beatrice Bevilacqua, Moshe Eliasof, Eli A. Meirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph GNNs by lcarning effective selection policies. In International Conference on Learning Representations, 2024.
Lue Brogat-Molle, Rémi Flamary, Céline Brouard, Juho Rousu, and Florence d' d'Alché Buc. Learning to predict graphs with fused Wasses-as barycenters. In International Conference on Machine Learning, 2022.
Stefan A. Burr. The mmthematics of networks. 1982.
Jingyu Chen, Rumlin Lei, and Zhewei Wei. PolyGCL: Graph contrastive learning via learnable spectral polynomial filters. In International Conference on Learning Representations, 2024.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. In International Conference on Learning Representations, 2021.
Michaöl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Tn Advances in Neural Information Processing Systems, 2016.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep bidi- rectional transformers for language understanding. Tn North American Chapler of the Association for Computational Linguistics, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorch Geometric. In Inter- national Conference on Learning Representations Workshops, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over-smoothing and over-squashing in deep graph neural networks. ACM International Conference on Information and Knowledge Management, 2023.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation lcarning on large graphs. In Advances in Newral Information Processing Systems, 2017.
Yuehui Han, Le Hui, Haobo Jiang, Jianjun Qian, and Jin Xie. Generative subgraph contrast for self- supervised graph representation learning. In European Conference on Computer Vision, 2022.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. IEEE/CVF International Conference on Computer Vision, pp. 1026 1034, 2015.
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with Chebyshev approximation, revisited. In Advances in Neural Informalion. Processing Systems, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Newral Information Processing Systems, 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Chang, and Yizhou Sun. GPT-GNN: Generative pre- training of graph neural networks. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020b.
Elvin Isufi, Fernando Gama, David Shuman, and Santiago Segarra. Graph filters for signal processing and machine learning on graphs. IEEE Transactions on Signal Processing, 2024.
Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph contrast for scalable sele-sup graph representation learning. IEEE International Conference on Data Mining, 2020.
Nikhil S. Ketkar. Deep learning with Python. In Apress, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations, 2015.
Thomas Kipf and Max Welling. Variational graph auto-encoders. In Advances in Neural Information Processing Systems- Workshops, 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Inter- national Conference on Learning Representations, 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Tn Advances in Newral Information Processing Systems, 2019.
Locheng Kong, Jiarui Feng, Hao Liu, Dacheng Tao, Yixin Chen, and Muhan Zhang. MAG-GNN: Rein- forcement learning boosted graph neural network. In Advances in Neural Information Processing Systems, 2023.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdel rahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: Denoising sequence-to-sequencc pre-training for natural language generation, translation, and comprehension. In Association for Computational Linguistics, 2019.
Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, and José H. Blanchet. A convergent singlc-loop algorithm for relaxation of Gromov- Wasscrstein in graph data, In International Conference on Learning Representations, 2023.
Ralph Linsker. Self-organization in perceptual network. Computer, 21:105-117, 1988.
Yunhui Liu, Huaisong Zhang, Ticke He, Tao Zheng, and Jianhua Zhao. Bootstrap latents of nodes and neighbors for graph self-supervised learning. In European Conference on Machine Learning and Knowledge Discovery in Databases, 2024.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiaoming Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In Advances in Neural Information Processing Systems, 2022.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127 163, 2000.
Facundo Mémoli. Cromov-Wasserrsere distances and the metric approach to object matching. Foundations of Computational Mathematics, 11:417 487, 2011.
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In International Workshop on Mining and Learning with Graphs, 2012.
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit MLE: Backpropagating through discrete exponential family distributions. In Advances in Neural Information Processing Systems, 2021.
Scbastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural samplers using variational divergence minimization. In Advances in Neural Information Processing Systems, 2016.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. ArXiu, abs/1905.09555 09350, 2019.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bring- ing order to the web. In The Web Conference, 1999.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: Graph contrastive coding for graph neural network pre-training. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 922ccnaa,, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Rliassi-Rad. Collec- tive classification in network data. volume 29, pp. 93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Advances in Neural Information Processing Systems Workshops, 2018.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009.
Shantanu Thakoor, Corentin Talloc, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Veličkovié, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representations, 2021.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Nenad Tomasev, Ioana Bica, Brian McWilliams, Lars Buesing, Razvan Pascanu, Charles Blundell, and Jovana Mitrovic. Pushing the limits of self-supervised ResNets: Can we outperform supervised learning without labels on ImageNet? In International Conference on Machine Learning Workshops, 2022.
Aäron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. ArXiv, abs/1807.0374 2018.
Titouan Vayer, Nicolas Courty, Romain Tavenard, Laetitia Chapel, and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning. 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph allention networks. In International Conference on Learning Representations, 2018.
Petar Veličkovié, William Fodus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In International Conference on Learning Regresenlations, 2019.
Cédric Villani el al. Optimal transporl: old and new, volume 338. Springer, 2009.
Haonan Wang, Jieyu Zhang, Qi Zhu, and Weitao Huang. Augmentation-free graph contrastive learning.
ArXio, abs/ 2////2204.4477. 2022.
Shuhei Watanabe. Tree-structured parzen estimator: Understanding its algorithm components and their roles for better empirical performance. ArXiu, abs/2304.11127, 2023.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32((): 4-24, 2021.
Teng Xiao, Zhengyu Chen, Zhimong Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for non-homophiloous graphs. In Advances in Neural Information Processing Systems, 2022.
Yaochen Xie, Zhao Xu, Zhengyang Wang, and Shuiwang Ji. Self-supervised lcarning of graph neural networks:
A unified review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45:2412-242 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Newral Information Processing Systems, 2020.
Mengyi Yuan, Minjie Chen, and Xiangei Li. MUSE: Multi-view contrastive learning for heterophilic graphs. ACM International Conference on Information and Knowledge Management, 2023.
Xuan Zang, Xianbing Zhao, and Buzhou Tang, Hierarchical molecular graph self-supervised learning for property prediction. Communications Chemistry, 6(1):34, 2023.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive represen- tation learning. Tn International Conference on Machine Learning Workshops, 2020b.
17

---

Published in Transactions on Machine Learning Research (03/2025)
A
Algorithm for FGWD
Algorithm Bregman Alternated Projected Gradient (BAPG) for FGWD
P - nud
AP 00
1+1
while (i < T) And (AP c) do
1/ Row updating
G - aM + 2(1 - LCC, C2) @ p(i-1) // Gradient of the objective function of Eq. 1 in p(i-1)
+ P(- @ (xp(-G/3)
+ diag( Pi...
_ P
// Column updating
G f- aM + 2(1 L C2) & P // Gradient of the objective function of Eq. in P
p(0 P exp(-G/1
P(0 p(0 diag( P(O) 1n
AP [P()_ p
i i+i+1
end while
B Evaluation on Larger Graphs
We compare FOSSILv2 with some basclines two large-scale graphs: OGBN-Arxiv and OGBN-Proteins, containing 1M and 30M edges, respectively (Hu et al. 2020a). For OGBN-Proteins, extract subgraph of 1M edges due to computational resource limitations. To this end, we use the NeighhorLoader loader of PyG to sample, for some nodes, 18 neighbors in each layer of its 3-hop neighborhood (Hamilton et al. 2017). Any number above 18 results in a number of edges that lead to a memory overflow with our method and all baselines. We show the results Table 7 Some baselines present. Table P result in memory overflow, therefore, they are not included in this experiment. We do not show results for DSSL in OGBN-Proteins because it does not work for graphs where we have disconnected regions. We observe that our method is competitive against the baselines.
Test accuracy on the node classification on large-scale graphs. The best results are highlighted bold, while the second best-performing methods are underlined.
Table 7:
Method
OGBN-Arxiv OGBN-Proteins
FS-GCN
30.75-0.32
88.67
FS-MLP
23. 23.16
88.7010.01
GSC
35.19 35.1920.36
88.87+0.01
GhC+Cheb
34.97 =0.53
88.6440.01
DSSL
58.36 12.69
BGRL
54.16 16300
89.3210.01
Subg-Con Con
60.82++0.0
89.04
FOSSILv2
56.22_0.12
88.63
C
Sensibility Analysis
One of the most important hyperparameters of FOSSIL a, which dictates how much our model should focus on each source of information of the input graph, namely, node features and graph structure. To assess how sensitive our framework is to the value of a, we vary its value and see how the performance changes.
18

---

Published in Transactions on Machine Learning Research (03/2025)
CiteSeer
PubMed
CoAuthor CS
100
Accurdey
Accurscy
60-
80
0.25
0.75
0.25
0.75
0.25
0.75
(a) Cora
(b) Citeseer
(c) PubMed
(d) CoAuthor-GG
Actor
Chameleon
Squirrel
14
35
Accuracy
Accuracy
344
52-
13
31
0.00
0.25
0.50
0.75
0.00
0.225
0.75
1.00
0.25
0.50
0.75
1.00
(0) Actor
(1) Chameleon
(g) Squirrel
Figure 3: Variation of the accuracy for several datasets w.r.t.
Specifically for each real-world dataset in our experiments, we fix the other hyperparameters and vary within the set {[0 0.1 1]}. For each value of a, we evaluate our method on 5 seeds and report the mean and standard deviation. Figure 3 shows the sensibility analysis results. We notice that the performance of our method can siguificantly change depending on the value a. Overall, for homophilic graphs, the best value of tends be close to 0.5. This suggests that node features and graph structure are equally important for the encoder characterize the graph. However, for heterophilic graphs, the best value of a tends to be close to 1. A plausible explanation is that even though the graph structure is important, the GCN encoder is not able to correctly exploit the structure of heterophilic graphs due to its intrinsic homophily assumption; our framework will rely more on node features. Hence, our encoder will converge to an MLP with a value of a close to 1. This further supports our idca to include a fcature extractor that is more suited to heterophilic graphs for future research.
19


Reviews:
[{"review_id": "AwuNaeyBVp", "reviewer": "Reviewer_hh1Z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n- The problem addressed is interesting, especially the applicability to heterophilic datasets.\n- Notation and experimental design are clear.\n\n### Weaknesses:\n- The paper is not easy to follow:\n   1) The method appears only on page 5, while an improved version (namely FOSSILv2) appears on page 12 in the Limitations section.\n   2) There is no clear and strong motivation behind each architectural choice. Authors should better clarify the rationale behind their choices. Specifically:\n\n         a) Why is each component necessary? \n\n         b) Why use GCN and GAT as backbones instead of GNNs designed for heterophilic graphs?\n\n         c) Why do the encoder and the generator use shared weights?\n\n         d) Why is the proposed decoupled encoder is more suitable for heterophilic graphs than current methods (including those designed to work in the heterophilic setting)?  \n   3) The authors split the Encoder section (Sec 4.2) into 2 subsections, which makes the text feel redundant and overcomplicated.\n   4) The figure and the text could be better linked.\n\n\n- The authors claim that current methods have GNN encoders that struggle with heterophilic datasets. Since the authors propose an encoder that is based on GCN, it is surprising that no comparison with methods specifically designed for heterophilic graphs, such as Geom-GCN [1], GCNII [2], or H_2GCN [3], is found to justify their choice.\n- OGBN-Arxiv is not cited in the list of cited datasets in Section 5, and it is missing from Tables 2, 3, 4, and 5.\n- Section 5.1 lacks important hyperparameters, such as the number of layers, the hidden dimension, optimizer, and number of epochs,  which limit the reproducibility of the experiments. \n- The authors split the development set into training and validation by considering 20 nodes per class for the training set and the rest for the validation set. Is this setting the same as in [4]? If so, the paper should be cited.\n- The authors should consider more recent homophilic and heterophilic tasks, such as [5], to strengthen their claim that FOSSIL works well with both homophilic and heterophilic graphs.\n\n\n### Minor issues:\n- Although it is clear, the acronym GNN is never defined.\n- Page 3: citep is not used correctly for GPR-GNN, ChebNetII, and PolyGCL.\n- Page 5: “the second [neural network] implements a GNN (Kipf & Welling, 2017)” . Is GNN a typo? Should GNN be replaced with GCN? \n- The titles of sections 5.3.1 and 5.3.2 are the same.\n- Table 1: a comma is missing in the Squirrel’s number of nodes.\n\n--------\n[1] Pei et al. Geom-GCN: Geometric Graph Convolutional Networks. ICLR 2020\n\n[2] Chen et al. Simple and Deep Graph Convolutional Networks. ICML 2020\n\n[3] Zhu et al. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS 2020\n\n[4] Shchur et al. Pitfalls of Graph Neural Network Evaluation. Relational Representation Learning Workshop, NeurIPS 2018\n\n[5] Luan et al. The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges. 2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Fused Gromov-Wasserstein Subgraph Contrastive Learning (FOSSIL), a self-supervised framework that captures both feature and structural similarities in graphs. Designed to work across varying levels of homophily, FOSSIL employs a decoupled encoding strategy and integrates node- and subgraph-level contrastive losses. Experimental results demonstrate good performance on diverse graph datasets compared to state-of-the-art methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses and minor issues.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mi3EVThwu8", "reviewer": "Reviewer_NhfX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The research topic is important, as designing effective pretext tasks can potentially reduce the number of required labeled data.\n2. The math is easy to understand, and the notation is clear.\n\n### Weaknesses\n1. The paper is very hard to follow, mainly because the method is not introduced until page 5. To improve readability, the authors should provide a high-level intuitive description of the method earlier in the paper. Delaying the overview and main method description until later pages makes it challenging to follow.\n2. The components of the architecture feel unmotivated. I think the authors should investigate more the need for certain components. For instance, the use of an additional GNN (GAT or GCN in the ablation study) to generate perturbations could be better motivated. The generator GNN, which takes the encoder output and performs additional message passing, effectively increases the receptive field for each node, resulting in representations that are not simple perturbations of the encoder outputs (as intended) but rather have a deeper view. This raises questions about whether the generated representations align with the intended objective.\n3. Sampling the subgraph breaks the equivariance of the architecture. I think the authors should at least discuss this point. I also believe that this would be more problematic if the datasets were not transductive.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a method that integrates node and subgraph level contrastive learning to be used a pretext task that generates representations later used for node level tasks. The architecture consists of an encoder, a generator which is responsible for generating perturbed views, and a fusion and subgraph sampling method that generates representations used in two contrastive learning losses, respectively for node and subgraph level.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical:\n1. Can you please clarify the need of each component? Mainly:\n\n    a. Related to what was discussed in the weaknesses. Why do you need to do additional message passing steps for obtaining perturbations? Can we only do for instance GAT at the feature level (or maybe just add some noise since we already have an embedding)? Note that these should be baselines for section 5.3.3.\n\n   b. Why do we need to remove the self loop in the gcn used to get the structure embedding? \n\n2. Results for ogbn-arxiv are missing from Tables 2,3,4,5 (which contain the baselines)\n3. The datasets used are a bit outdated and also small. I think the authors should experiment more with the ogb datasets, and minimally  include ogbn-products and ogbn-proteins, which are medium scale datasets.\n\n### Nice to have:\n1. What is the impact of including the node degree in the fusion model? This part also feels a bit unmotivated, so at least having an ablation study on it would strengthen the paper.\n2. On a more general note, why only testing on node prediction tasks? Does it mean that we need a pretext task for each graph task, instead of a single pretext task that can be used for many graph tasks (node prediction, graph prediction, link prediction)? \n3. There are many works to sample subgraphs in subgraph gnns ([1,2,3] for instance), so please add these references. Also, I think it would be interesting to consider these more convoluted and generally better performing sampling strategies.\n\n### Minor issues:\n1. citet/citep is not used correctly in page 3 (Section 2.2)\n2. equation pointer in page 8 is broken (i.e., it says equation ??)\n3. title of section 5.3.1 is wrong, as that is the title of section 5.3.2\n\n[1] Qian et al. Ordered Subgraph Aggregation Networks\n\n[2] Kong et al. MAG-GNN: Reinforcement Learning Boosted Graph Neural Network\n\n[3] Bevilacqua et al. Efficient Subgraph GNNs by Learning Effective Selection Policies", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "P3d74aJAOS", "reviewer": "Reviewer_TVUs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The authors motivate the need for SSL on graphs and existing gaps using solid literature review.\n2. Notations and Problem Setup is very clear.\n3. Proposing the Fused GWD as a loss function is novel. This is a simple and effective solution to fill the gap in existing Subgraph CL methods.\n\nWeaknesses:\n1. The authors claim that CL on graphs is hard because generating positive pairs is hard without any references. \n2. The authors claim that their architecture is robust to various homophily levels within the graph dataset. It is not clear whether the authors refer to distinct datasets with different homophily levels or graphs having different homophily levels within the same dataset. If it is the latter, there needs to be more experiments. If not, it needs revision.\n3. The authors mention the transformation through first encoder as \"linear projection\" which is incorrect. It has a non-linearity as shown in Equation (6), which does not make it a linear projection.\n4. It is not clear how \"Fusion\" is different from a standard GCN/MPNN framework (with self-loops). The process is similar to scaling the aggregated messages. \n5. Subsection 5.3.1 and 5.3.2 have the same headings \"Impact of decoupled node embeddings\". This is a typo.\n6. The authors do not explain what the \"Overall\" column is in any of their results.\n7. In Table 3, the performance of GWD is alarming. This means $\\alpha=0$. The authors do not explain why GWD performs bad on homophilic graphs, where the subgraph structure information should actually be helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors identify that to improve SSL on graphs, the CL loss needs to incorporate both feature information usually captured by Wasserstein Distance (WD) and subgraph structural information usually captured by Gromov-Wasserstein Distance (GWD). The authors also point out that heterophily posts a significant challenge when generating positive-negative pairs. To fill this gap, the authors propose the FOSSIL - Fused Gromov-Wassertein Subgraph Contrastive Learning:\n1. An learnable linear combination of WD and GWD to balance the structural information and feature information as a contrastive loss function.\n2. A 2-stage training strategy for GNNs to tackle heterophily: (1) Use Identity matrix as adjacency to transform just the node embeddings (MLP behavior) and (2) Without adding self-loops (usually done in MPNNs), do message-passing. Finally fuse (1) and (2) using linear combination determined by an MLP. \n\nThey conduct extensive experiments on self-supervised node-classification task and evaluate their design choice, which show that FOSSIL shows competitive performance, especially on heterophilic graphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the concerns mentioned in the weaknesses and adjust the submission. Additionally, W7 is very concerning. It is unclear why GWD fails consistently on all kinds of graphs. The ablation does not help to understand the imporance of FGWD. I suggest to perform the following ablation: Using standard GCN, ablate on subgraph similarity metric. This is help us isolate the benefit of FGWD.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zoiJudg5Aw", "reviewer": "Reviewer_STEg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\n\nFOSSIL captures both node features and graph structure simultaneously. This is a significant strength as previous methods often treat these aspects separately, leading to suboptimal performance.\n\nDespite good experimental results, the paper further addresses potential scalability issues by proposing FOSSILv2. FOSSILv2 reduces the memory complexity of the node-level contrastive loss so that the method can handle larger graphs.\n\n### Weakness\n\nThe paper is generally well-written. However, the formal problem statement is missing. The paper only outlines general issues in contrastive graph learning, and then directly introduces the methodology. It does not provide an explicit and concise problem definition. Readers without much background knowledge of contrastive graph learning will find it difficult to follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "T\bhis paper introduces a new contrastive learning framework for graph representation learning, termed Fused Gromov-Wasserstein Subgraph Contrastive Learning (FOSSIL). The advantage of FOSSIL is three-fold:\n\n1. FOSSIL adopts Fused Gromov-Wasserstein Distance (FGWD) in the training loss, which can integrate both structural and feature similarities in a unified contrastive learning framework.\n\n2. FOSSIL involves a decoupled embedding design to work well across both homophily and heterophily graphs. \n\n3. FOSSIL dynamically generates subgraph augmentations by Graph Attention Network (GAT). This provides a learnable and adaptive approach to data perturbation. \n\nExperiment results are provided to validate the benefit of FOSSIL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Add a formal problem definition of the problem definition of contrastive graph learning, and briefly introduce its motivation (e.g., how it can be used in downstream problems).\n\nIn Eq. (5), the author introduces an MLP of input dimension $\\mathbb{R}^{N\\times D\\times N\\times D\\times N}$, which is too high. Please check.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Please clarify the remaining concerns raised by reviewer NhfX. Specifically, quoting from the discussion with the Reviewer:

1."I am not sure you have been answering the intended question, but I may be wrong. My initial point was that the generator GNN (which can be GAT) should not use  (and can therefore only use ). This is because the generator GNN should not do additional message passing. Can you please clarify if you tried this variant and how is this called in section 5.3.3?" -- Please address this question in your camera ready revision.

2."Yes your encoder is certainly equivariant. It is the sampling that breaks equivariance." -- Please add a discussion that reflects this point in the camera ready version.

3."Can you please add the requested experiment on ogbn-proteins? I think waiting one additional week is fine, given that this experiment was requested on December 7th. OGBN-Arxiv is not sufficient as arxiv is considered a small dataset in the ogb website (1,166,243 edges) while proteins is considered medium (39,561,252 edges, therefore around 33 times larger)." -- Please add results on the requested dataset.
Decision: Accept (poster)