Fast and Featureless Node Representation Learning with Partial Pairwise Supervision Sujan Chakraborty1 and Saptarshi Bej1*
arXiv:2605.19916v1 [cs.LG] 19 May 2026
1*
School of Data Science, Indian Institute of Science Education and Research, Thiruvananthapuram, 695551, Kerala, India .
*Corresponding author(s). E-mail(s): [email protected]; Contributing authors: [email protected]; Keywords: Contrastive Learning, Node Representation Learning, Modularity Optimization, Pairwise Supervision, Network Embedding
We introduce Contrastive FUSE, a fast and unified framework for scalable node representation learning in graphs with partially available pairwise node labels and no available node features. Unlike existing methods, we directly optimize a spectral contrastive objective that integrates community-aware structural signals with signed pairwise constraints. To support large-scale training, we replace the expensive modularity gradient with a lightweight approximation, which preserves the structure-seeking behavior of modularity while reducing the computational cost significantly. This yields an efficient optimization scheme with a natural gradient decomposition and adaptive learning-rate scaling, enabling fast iterative updates even on million-edge graphs. Extensive experiments on benchmark citation networks, large co-purchase graphs, and OGB datasets show that Contrastive FUSE achieves competitive or superior contrastive classification performance without relying on node features, while offering substantial runtime gains over existing baselines. These results highlight the effectiveness of coupling modularity-inspired structural learning with contrastive supervision for efficient and scalable contrastive node representation learning.
1 Introduction Learning meaningful node representations is a fundamental problem in graph learning, with applications spanning social networks, biological interaction networks, recommendation systems, and scientific knowledge graphs. The goal is to embed nodes 1
into a low-dimensional vector space such that structural properties of the graph and task-relevant relationships are preserved. A long line of work has explored unsupervised graph embedding methods based on random walks, spectral decompositions, and autoencoding architectures, including DeepWalk [1], Node2Vec [2], and variational graph autoencoders (VGAE) [3]. More recently, self-supervised methods such as DGI [4], GRACE [5], and SGCL [6] have adopted augmentation-based contrastive learning objectives that maximize agreement between representations of the same node under different perturbations while contrasting them against other nodes. In this work, we consider a different notion of contrastive learning. Rather than relying on augmentation-based agreement, we study node classification under partially observed pairwise supervision in featureless or feature-sparse graphs. Specifically, we assume that supervision is available in the form of pairwise constraints indicating whether two nodes should be considered similar or dissimilar, while explicit node attributes are unavailable, unreliable, or non-transferable across graph instances [7, 8]. Our goal is to learn discriminative node embeddings directly from graph structure and pairwise constraints in a fast and scalable manner. This setting arises naturally across several domains. In computational biology, many problems are fundamentally defined through pairwise relationships. For example, synthetic lethality prediction models genes as nodes in a protein–protein interaction network, with supervision provided through lethal and non-lethal gene pairs. Similarly, protein–protein interaction and drug–target interaction prediction often rely primarily on structural connectivity because node attributes are incomplete, noisy, context-dependent, or unavailable for newly observed entities [9, 10]. In recommendation systems, implicit feedback such as clicks or purchases is naturally represented through pairwise preference signals, while explicit user or item features are often sparse or unreliable [11, 12]. In privacy-sensitive settings such as healthcare or social networks, node attributes may be inaccessible due to legal or institutional constraints, making structure-only learning necessary [7]. Across these settings, supervision naturally exists in pairwise form, while embeddings must often be recomputed efficiently for evolving or context-specific graphs. To address this problem, we propose Contrastive FUSE, a fast and scalable framework for learning node embeddings from graph structure and pairwise constraints. The central idea is to augment the classical modularity maximization objective with a signed, normalized contrastive Laplacian constructed from labeled node pairs. This formulation encourages embeddings of similar node pairs to move closer while explicitly separating dissimilar pairs, all while preserving the global structural organization of the graph. To enable scalable optimization, we further introduce an efficient approximation of the modularity gradient that preserves its structure-seeking behavior while significantly reducing computational overhead. The resulting optimization procedure uses iterative gradient ascent with row-wise projection and avoids the need for deep encoders, graph augmentations, or expensive message-passing architectures. We evaluate Contrastive FUSE on a diverse collection of benchmark datasets, including citation networks, co-purchase graphs, and large-scale OGB datasets. Across
2
a wide range of settings, the proposed method achieves competitive or superior downstream node classification performance while requiring substantially lower runtime than existing contrastive baselines. Our main contributions are summarized as follows: 1. We introduce a novel contrastive formulation for node representation learning under pairwise supervision, directly integrating labeled node-pair constraints into the embedding objective for featureless or feature-sparse graphs. 2. We propose a signed, normalized contrastive Laplacian that augments modularity-based structural learning by simultaneously attracting similar node pairs and repelling dissimilar node pairs in the embedding space. 3. We develop a computationally efficient optimization scheme based on an approximation of the modularity gradient, enabling fast and scalable training while preserving the structural regularization properties of modularity maximization.
2 Related Work Spectral clustering has long served as a foundational framework for graph partitioning and community detection. Classical approaches construct low-dimensional node embeddings by eigendecomposing variants of the graph Laplacian, with the objective of minimizing cut-based criteria such as the normalized cut [13]. Closely related to spectral cuts, modularity maximization [14] seeks partitions that exhibit higher intra-community edge density than expected under a random null model, and can be interpreted as optimizing a quadratic form over the modularity matrix. Early modularity-based algorithms, such as Louvain, relied on greedy heuristics and were not amenable to end-to-end optimization. More recent efforts have sought to integrate modularity into differentiable learning pipelines. For instance, Deep Modularity Networks (DMoN) [15] introduced a relaxed modularity objective within Graph Neural Networks (GNNs), while DGCLUSTER [16] optimized modularity-based losses for attributed graphs. Although effective in unsupervised settings, these approaches optimize modularity through feature-driven neural encoders, implicitly relying on node features and deep architectures, and do not accommodate explicit pairwise supervision. Graph Contrastive Learning (GCL) has emerged as a dominant paradigm for selfsupervised node representation learning. Methods such as DGI [4], GRACE [5], and GraphCL [17] construct multiple augmented views of a graph and optimize InfoNCEstyle objectives that maximize agreement between embeddings of the same node across views while contrasting them against other nodes. These approaches learn representations by enforcing invariance to stochastic perturbations, and typically rely on deep encoders, extensive data augmentations, and large numbers of negative samples. To address the semantic instability introduced by random augmentations, recent work has explored spectral interpretations of contrastive objectives. COLES [18] reformulated Laplacian Eigenmaps within a contrastive framework, showing that spectral alignment can be viewed as a form of contrastive learning without explicit augmentations. Similarly, EigenMLP [19] and SpCo [20] proposed spectral encoders that are
3
invariant to eigenvector perturbations, highlighting the compatibility between contrastive learning and spectral methods. Complementary directions include CCA-SSG [21], which replaces negative-sample-based objectives with canonical correlation maximization between graph views, and MVGRL [22], which learns representations through contrastive agreement across diffusion-based multi-view graph augmentations. On the other hand, pairwise supervision in the form of must-link and cannotlink constraints has been extensively studied in the context of constrained clustering [23]. Such constraints can be incorporated through modified Laplacians or generalized eigenvalue problems, offering theoretical guarantees and closed-form solutions. These ideas naturally align with contrastive principles, as positive constraints encourage proximity while negative constraints enforce separation in the embedding space. Signed graph learning further formalizes this perspective by modeling both attractive and repulsive relationships. Methods such as SGCN [24] and SGCL [6] extend GCNs with signed convolutions that pull positive neighbors together and push negative neighbors apart. Subsequent extensions, including SBGCL [25] and BA-SGCL [26], adapt these ideas to bipartite and adversarial settings. In the spectral domain, signed Laplacians [13, 27] generalize classical spectral clustering to signed networks by explicitly encoding attraction and repulsion. While these approaches leverage pairwise relations, they often depend on deep architectures or are not designed to jointly integrate pairwise supervision with community-aware structural objectives such as modularity that capture global structure of the graph as well as preserve pairwise supervision signals. Our work adopts a task driven contrastive formulation that directly incorporates supervision signals from partially observed pairwise node labels. Rather than using modularity as an unsupervised or pretraining objective, we integrate a modularityinspired structural term directly into the supervised optimization problem. This results in a unified objective that simultaneously promotes community structure and enforces contrastive pairwise constraints, enabling fast and scalable learning of node embeddings in the absence of node features.
3 Problem Statement Let G = (V, E ) be an undirected graph with |V | = n nodes Pand adjacency matrix P A∈ Rn×n . Let d ∈ Rn denote the degree vector, where di = j Aij , and m = 21 i,j Aij be the total number of edges. In addition to graph structure, we are given a set of pairwise supervisory signals encoded by a matrix
Y ∈ {−1, 0, +1}n×n , where
+1, if (i, j ) is a positive pair (e.g., same class), Yij = −1, if (i, j ) is a negative pair, 0, if the pair is unlabeled. 4
3.1 Objective Our goal is to learn a low-dimensional node embedding matrix
S = [S1 , . . . , Sn ]⊤ ∈ Rn×k ,
k ≪ n,
such that: 1. nodes connected by positive pairs are embedded close together, 2. nodes connected by negative pairs are embedded far apart, and 3. the embeddings preserve community structure induced by the graph. This has been achieved by integrating information from a structural and a contrastive term as described in the next Section.
4 Contrastive FUSE Algorithm 4.1 Learning Goal Our goal is to learn a node embedding matrix
⊤ S1 .. S = . ∈ Rn×k ,
Si ∈ Rk ,
Sn⊤
that simultaneously satisfies the following properties: 1. Structural coherence: nodes that exhibit higher internal connectivity are encouraged to have similar embeddings. 2. Pairwise consistency: positive pairs (i, j ) ∈ P+ should be embedded close together, while negative pairs (i, j ) ∈ P− should be embedded far apart.
4.2 Modeling Structural Coherence We adapt a slightly modified version of modularity as defined in [14] to accommodate continuous valued high-dimension node feature learning. Our adaptation is as follows
Q(S ) =
1 X di dj Aij − Si⊤ Sj , 2m i,j 2m
(1)
P where A denotes the adjacency matrix, di = j Aij is the degree of node i, and P 1 m = 2 i,j Aij is the total number of edges. In matrix form, this expression reduces to Q(S ) =
1 Tr S ⊤ BS , 2m 5
(2)
where
B =A−
dd⊤ 2m
is the modularity matrix.
4.2.1 Gradient Approximation Differentiating Q(S ) with respect to S yields the exact gradient
∇S Qexact =
1 m
AS −
1 d d⊤ S . 2m
(3)
While this expression faithfully captures the modularity objective, the degree– degree correction term d(d⊤ S ) introduces both numerical instability and increased computational cost for large and dense graphs. To address this, we adopt a linearized approximation in which the weighted degree aggregation d⊤ S is replaced by the unweighted global sum 1⊤ S , yielding the proposed gradient 1 1 ⊤ ∇S Qprop = d 1 S , (4) AS − 2m 2m
Pn where 1 denotes the all-ones vector and 1⊤ S = i=1 Si . In Section 7, we formally show that the ascent direction induced by ∇S Qprop remains closely aligned with that of ∇S Qexact , with a cosine similarity bounded away from zero under mild assumptions on the embedding distribution and graph degree structure. This establishes the theoretical validity of the proposed approximation while enabling improved numerical stability and scalability. A detailed experiment on the exact vs approximate gradient approximation has been reported in Appendix A.5.
4.3 Modeling Pairwise Consistency In addition to graph structure, we assume access to a set of labeled node pairs
P = {(i, j, yij )},
yij ∈ {+1, −1},
where yij = +1 indicates that nodes i and j belong to the same class, while yij = −1 indicates that they belong to different classes. We encode this supervision in a sparse signed pair matrix +1, (i, j ) ∈ P+ , Yij = −1, (i, j ) ∈ P− , 0, otherwise. The contrastive degree of node i is defined as
Dc,ii =
X j
6
|Yij |,
and the associated signed normalized Laplacian is given by
Lc = I − Dc−1/2 Y Dc−1/2 . This operator penalizes violations of pairwise constraints: positive pairs encourage similarity between embeddings, while negative pairs encourage oppositeness. Such signed Laplacians are standard in the analysis of signed graphs and contrastive relations as can be found in [18].
4.4 Contrastive FUSE Objective Combining signals arising from structural coherence and pairwise consistency, the Contrastive FUSE objective is defined as
e ) − λ Tr(S ⊤ Lc S ), J (S ) = Tr(S ⊤ BS where ⊤
e = A − d1 , B 2m and λ > 0 and controls the relative strength of contrastive supervision.
4.4.1 Interpretation of the Contrastive Laplacian Term We analyze the quadratic form induced by the signed contrastive Laplacian
Lc = I − Dc−1/2 Y Dc−1/2 , where Y ∈ {−1, 0, +1}n×n encodes pairwise supervision and
Dc,ii =
X
|Yij |
j
denotes the contrastive degree of node i. By expanding the trace, we obtain
Tr(S ⊤ Lc S ) = Tr(S ⊤ S ) − Tr S ⊤ Dc−1/2 Y Dc−1/2 S . The first term satisfies Tr(S ⊤ S ) =
n X
∥Si ∥22 ,
i=1
where Si denotes the i-th row of the embedding matrix S . For the second term, let
B := Dc−1/2 Y Dc−1/2 . 7
Using the trace identity Tr(S ⊤ BS ) =
X
Bij ⟨Si , Sj ⟩,
i,j
where Si denotes the i-th row of S , we obtain
X Tr S ⊤ Dc−1/2 Y Dc−1/2 S = Dc−1/2 Y Dc−1/2 ⟨Si , Sj ⟩. ij
i,j −1/2
Since Dc
is diagonal with 1 , Dc,ii
(Dc−1/2 )ii = p the (i, j )-th entry of B satisfies
Dc−1/2 Y Dc−1/2
Yij p . Dc,ii Dc,jj
=p
ij
Substituting this expression into the trace expansion yields
Yij p ⟨Si , Sj ⟩. Dc,ii Dc,jj
X p Tr S ⊤ Dc−1/2 Y Dc−1/2 S = i,j
Equivalently, this can be written as
X Tr S ⊤ Dc−1/2 Y Dc−1/2 S = Yij
*
i,j
S S p i ,p j Dc,ii Dc,jj
+ .
Since Yij ∈ {−1, 0, +1}, we decompose it as
Yij = |Yij | · yij ,
yij ∈ {+1, −1},
which allows us to rewrite the quadratic form as
* Tr(S ⊤ Lc S ) =
X i
∥Si ∥22 −
X i,j
|Yij |
S S p i , yij p j Dc,ii Dc,jj
To obtain a distance-based interpretation, we apply the identity
∥a − b∥22 = ∥a∥22 + ∥b∥22 − 2⟨a, b⟩ 8
+ .
to the specific substitutions
Si , Dc,ii
Sj . Dc,jj
a= p
b = yij p
− ⟨a, b⟩ =
1 ∥a − b∥22 − ∥a∥22 − ∥b∥22 . 2
Rearranging terms yields
Substituting this expression back into the sum and collecting terms, we arrive at the final form 2 X |Yij | Si Sj ⊤ p Tr(S Lc S ) = − yij p . 2 Dc,ii Dc,jj i,j 2
Geometric Interpretation This expression reveals that the contrastive Laplacian penalizes pairwise distances in the embedding space in a supervision-aware manner. For a positive pair (i, j ) with yij = +1, the penalty term becomes S S p i −p j Dc,ii Dc,jj
2
, 2
which encourages the embeddings of nodes i and j to be close, promoting similarity. In contrast, for a negative pair (i, j ) with yij = −1, the term reduces to
S S p i +p j Dc,ii Dc,jj
2
, 2
which is minimized when Si and Sj point in p opposite directions, thereby explicitly enforcing dissimilarity. The normalization by Dc,ii ensures that nodes with many contrastive relationships do not dominate the objective. Overall, the term Tr(S ⊤ Lc S ) acts as a signed, normalized pairwise regularizer that pulls positive pairs together while pushing negative pairs apart in the embedding space.
4.5 Optimization We optimize J (S ) via projected gradient ascent. The approximation of ∇S Qexact to ∇S Qprop as discussed in Section 4.2 induces the structural gradient (upto a proportionality constant) derived from the first term of J (S )
e Gmod = BS. 9
Pairwise supervision is incorporated through the contrastive gradient
Gcon = −Lc S. derived from the second term of J (S ). At each iteration, gradients from structural and contrastive components are combined as G = Gmod + λ Gcon , followed by a gradient ascent update
Se = S + η G, where η > 0 is the step size. To prevent trivial scaling solutions and ensure comparable embedding magnitudes across nodes, we project onto the constraint set
∥Si ∥2 = 1,
∀i ∈ V,
via row-wise normalization:
Si ←
Sei . ∥Sei ∥2
This procedure yields embeddings that encode both community structure and pairwise contrastive information. A pipeline for this algorithm can be seen in Fig 3.
4.6 Pairwise Classification Given a node embedding matrix S ∈ Rn×k obtained from an embedding method such as Contrastive FUSE, DeepWalk, Node2Vec, or the other baselines we perform pairwise classification using a graph neural network (GNN)–based classifier.
4.6.1 GNN-based Refinement The initial embeddings S are treated as node features and passed through a GNN encoder fGNN (·), instantiated as a GCN, GAT, or GraphSAGE network:
Z = fGNN (S, A),
′
Z ∈ Rn×d ,
where A is the adjacency matrix of the graph and Zi denotes the refined embedding of node i.
4.6.2 Pairwise Representation For a given node pair (i, j ), a pairwise representation is constructed by concatenating the corresponding node embeddings: ′
hij = [ Zi ∥ Zj ] ∈ R2d . 10
Algorithm 1 Contrastive FUSE Input: Graph adjacency matrix A, degree vector d, contrastive pair matrix Y , embedding dimension k , learning rate η , contrastive weight λ, number of iterations T Output: Node embedding matrix S ∈ Rn×k 1: Construct the modularity matrix: ⊤
e ← A − d1 , B 2m 2:
m=
1X Aij 2 i,j
Construct the contrastive Laplacian:
Dc ← diag(|Y |1),
Lc ← I − Dc−1/2 Y Dc−1/2
Initialize S ∈ Rn×k with random vectors 4: Normalize rows of S : Si ← Si /∥Si ∥2 5: for t = 1 to T do 6: Compute structural gradient: 3:
e Gmod ← BS 7:
Compute contrastive gradient:
Gcon ← −Lc S 8:
Gradient ascent update:
Se ← S + η Gmod + λGcon 9:
Project onto constraint set (row normalization):
Si ← 10: 11:
Sei , ∥Sei ∥2
∀i ∈ V
end for return S
4.6.3 Similarity Prediction The pair embedding hij is passed through a multi-layer perceptron (MLP) similarity head g (·) to produce a scalar similarity score:
ŷij = g (hij ), which is interpreted as the probability that the pair (i, j ) belongs to the positive class. 11
Dataset Cora CiteSeer PubMed Amazon Photo WikiCS ArXiV Products
# Nodes 2,708 3,327 19,717 7,487 11,701 1,69,343 2,449,029
# Edges 5,429 9,104 44,338 119,043 216,123 1,166,243 61,859,140
# Classes 7 6 3 8 10 40 47
Given Emb Dim. 1,433 3,703 500 745 300 128 100
Table 1: Statistics of the benchmark datasets used in the experiments.
4.6.4 Training Objective The classifier is trained using a binary cross-entropy loss over labeled pairs:
LBCE = −
Xh
i yij log σ (ŷij ) + (1 − yij ) log 1 − σ (ŷij ) ,
(i,j)
where yij ∈ {0, 1} denotes the ground-truth pair label and σ (·) is the sigmoid function. This contrastive GNN-based classifier enables effective evaluation of learned embeddings on downstream pairwise prediction tasks.
5 Experiments 5.1 Datasets We evaluate the proposed Contrastive FUSE framework on a diverse set of benchmark graph datasets covering citation networks, co-purchase graphs, and large-scale academic graphs. Specifically, we use Cora [28], CiteSeer [29], PubMed [30], WikiCS [31], Amazon Photo [32], and the large-scale OGBN-ArXiv [33] and OGBN-Products [33] datasets, details of which have been given in Table 1. The first five datasets are treated as medium-scale graphs and results are reported as averages across them. OGBN-ArXiv and OGBN-Products are used exclusively for scalability analysis because of their substantially larger size and higher density.
5.2 Baselines We compare Contrastive FUSE against a broad range of unsupervised and selfsupervised node embedding methods to validate its efficacy. For unsupervised structural baselines, we employ DeepWalk [1], Node2Vec [2], which rely on random walks to capture neighborhood locality, as well as VGAE [3] as a representative generative baseline. To represent state-of-the-art self-supervised approaches, we include DGI [4], which maximizes mutual information between local and global patch representations, and GRACE [5], which utilizes augmentation-based contrastive learning. We further include COLES [18], a spectral contrastive method based on Laplacian Eigenmaps, CCA-SSG [21], which learns invariant graph representations through canonical correlation maximization without negative sampling, and MVGRL [22], which performs 12
multi-view contrastive learning using diffusion-based graph augmentations. Given the signed nature of our objective, we also compare against SGCL [6], a contrastive method explicitly designed for signed graphs. Apart from these, we include a low- and highend baseline, namely Random (embeddings drawn from a Gaussian distribution) and Given (Word2Vec-derived embeddings provided along with the datasets), respectively.
5.3 Experimental Setup Unless otherwise stated, Contrastive FUSE is trained with scaled parameters ηscaled = 105 and λscaled = 0.75 for all datasets except ArXiv and Products. For OGBN-ArXiv and OGBN-Products, we use ηscaled = 106 and λscaled = 0.5 to accommodate the higher graph density. To ensure stability across different numbers of contrastive pairs and graph densities, the effective learning rate and contrastive weight are adapted as:
5000 p∗ = max 0.25, , P
1 d∗ = √ , d¯
p∗ . d∗ where P , p∗ , d∗ and d¯ corresponds to the number of pairs, pair scaling factor, density scaling factor and average degree of the graph respectively. η = ηscaled · p∗ · d∗ ,
λ = λscaled ·
5.3.1 Pair Construction Protocol Sampling strategy and relation to labels. : Let (V = 1, . . . , n) denote the node set with labels (ℓ : V → 1, . . . , C ). We construct a set of contrastive pairs (P = P + ∪ P − ), where P + ⊆ (i, j ) : ℓ(i) = ℓ(j ), , i ̸= j, P − ⊆ (i, j ) : ℓ(i) ̸= ℓ(j ). Each pair is labeled as (yij = +1)f or((i, j ) ∈ P + ) and (yij = −1) for ((i, j ) ∈ P − ). Thus, pairwise supervision is directly aligned with class (and often community) structure. Positive/negative ratio. : We adopt a balanced sampling strategy with |P + | =
P 2
,
|P − | = P − |P + |,
ensuring an approximately equal proportion of positive and negative pairs, which stabilizes contrastive learning.
Sampling procedure. : Pairs are sampled uniformly at random within each set (P + ) and (P − ). For classes with limited nodes, sampling with replacement is used when necessary to maintain the desired number of pairs. All sampling is controlled via a fixed random seed to ensure reproducibility.
13
Handling of trivial (easy) pairs. : We do not explicitly filter “easy” pairs (e.g., nodes that are already structurally close or distant). Instead, the sampling remains unbiased, resulting in a natural mixture of easy and hard pairs. This avoids introducing additional heuristics and provides a stable training signal in practice. Relation to graph structure. : Importantly, pair labels are derived solely from node labels and not from structural proximity (e.g., adjacency or shortest paths). This ensures that the contrastive supervision provides complementary information to the structural objective, rather than redundantly encoding graph topology. For downstream evaluation, embeddings are used as input features to Logistic Regression, as well as to GCN [34], GAT [35], and GraphSAGE [36] classifiers trained for 100 epochs using Adam with a learning rate of 0.001. GCN, GAT and GraphSAGE are used to further refine the embeddings which are finally concatenated and classified pairwise through an MLP. Results are averaged over contrastive pair counts of 50k, 100k, and 500k across five runs. Evaluation metrics include Accuracy and Macro-F1.
6 Results 6.1 Downstream Classification Performance Table 2 reports downstream classification performance averaged across Cora, CiteSeer, PubMed, WikiCS, and Amazon Photo. Contrastive FUSE consistently achieves the best or near-best performance across all classifiers. It is to be noted that our algorithm Contrastive FUSE has hereby been denoted as ContFUSE throughout the tables and figures. Baselines like COLES and MVGRL failed to run on larger datasets like ArXiV and showed a memory error. Under Logistic Regression, Contrastive FUSE improves both accuracy and macroF1 compared to unsupervised baselines, demonstrating the benefit of incorporating pairwise supervision at the embedding stage. When combined with GNN classifiers (GCN, GAT, GraphSAGE), Contrastive FUSE either matches or outperforms all competing methods, highlighting its compatibility with message-passing architectures. Table 3 presents scalability results on the OGBN-ArXiv dataset. Despite using fewer computationally expensive operations than other contrastive methods, Contrastive FUSE achieves competitive performance across all classifiers. In particular, Contrastive FUSE maintains strong performance under both shallow (Logistic Regression) and deep (GCN/GAT/GraphSAGE) classifiers, confirming its robustness at scale. Further analysis for the OGBN-Products dataset can be found in Appendix A.4.
6.2 Runtime Efficiency Runtime comparisons are reported in Table 4 for medium-scale datasets and Table 5 for OGBN-ArXiv. On medium-scale graphs, Contrastive FUSE is significantly faster than contrastive baselines such as GRACE and SGCL, while remaining competitive with DGI (which takes lesser time than ContFUSE but compromises in performance). 14
Logistic Embedding DeepWalk DGI ContFUSE GRACE Node2Vec Random Given SGCL VGAE COLES CCA-SSG MVGRL
GAT
Acc
F1
Acc
F1
0.498 ± 0.005 0.499 ± 0.006 0.505 ± 0.022 0.499 ± 0.006 0.496 ± 0.005 0.502 ± 0.003 0.497 ± 0.005 0.499 ± 0.005 0.499 ± 0.006 0.498 ± 0.003 0.498 ± 0.005 0.502 ± 0.011
0.495 ± 0.011 0.502 ± 0.009 0.531 ± 0.031 0.502 ± 0.013 0.496 ± 0.013 0.502 ± 0.009 0.494 ± 0.013 0.501 ± 0.012 0.499 ± 0.018 0.500 ± 0.009 0.500 ± 0.012 0.512 ± 0.018
0.759 ± 0.012 0.562 ± 0.009 0.762 ± 0.010 0.586 ± 0.016 0.756 ± 0.009 0.513 ± 0.006 0.691 ± 0.017 0.620 ± 0.013 0.729 ± 0.013 0.612 ± 0.015 0.579 ± 0.049 0.523 ± 0.078
0.767 ± 0.012 0.655 ± 0.032 0.769 ± 0.011 0.675 ± 0.024 0.765 ± 0.011 0.622 ± 0.040 0.734 ± 0.017 0.675 ± 0.025 0.741 ± 0.011 0.664 ± 0.036 0.650 ± 0.037 0.644 ± 0.045
GCN Embedding DeepWalk DGI ContFUSE GRACE Node2Vec Random Given SGCL VGAE COLES CCA-SSG MVGRL
GraphSAGE
Acc
F1
Acc
F1
0.749 ± 0.017 0.552 ± 0.007 0.751 ± 0.012 0.591 ± 0.014 0.747 ± 0.015 0.514 ± 0.006 0.685 ± 0.016 0.618 ± 0.014 0.723 ± 0.016 0.606 ± 0.015 0.581 ± 0.019 0.518 ± 0.048
0.756 ± 0.013 0.621 ± 0.037 0.756 ± 0.011 0.663 ± 0.022 0.753 ± 0.012 0.602 ± 0.045 0.715 ± 0.019 0.655 ± 0.028 0.734 ± 0.011 0.648 ± 0.025 0.637 ± 0.008 0.610 ± 0.039
0.739 ± 0.017 0.566 ± 0.015 0.758 ± 0.010 0.597 ± 0.012 0.732 ± 0.019 0.509 ± 0.004 0.674 ± 0.013 0.618 ± 0.010 0.703 ± 0.013 0.619 ± 0.014 0.597 ± 0.013 0.516 ± 0.049
0.745 ± 0.015 0.649 ± 0.036 0.759 ± 0.009 0.676 ± 0.023 0.738 ± 0.018 0.602 ± 0.043 0.709 ± 0.013 0.657 ± 0.034 0.719 ± 0.013 0.656 ± 0.032 0.654 ± 0.031 0.653 ± 0.043
Table 2: Downstream classification performance averaged across all small to medium sized datasets. The best and second best performances are highlighted in bold and underlined respectively.
On OGBN-ArXiv, Contrastive FUSE achieves a favorable trade-off between performance and efficiency: it is approximately 13–14× faster than random-walk–based methods such as DeepWalk and Node2Vec, with only a modest 3–4% reduction in classification performance. Several baselines fail to scale to ArXiv due to memory constraints, whereas Contrastive FUSE remains tractable. Overall, these results demonstrate that Contrastive FUSE provides a strong balance between predictive performance, scalability, and computational efficiency. 15
Logistic Acc F1
Embedding DeepWalk DGI ContFUSE Node2Vec CCA-SSG Random Given
0.500 0.499 0.506 0.499 0.502 0.499 0.498
0.502 0.518 0.574 0.505 0.506 0.504 0.500
GAT Acc F1 0.627 0.504 0.626 0.615 0.504 0.508 0.515
0.665 0.668 0.668 0.656 0.638 0.552 0.625
GCN Acc F1 0.699 0.499 0.644 0.663 0.507 0.511 0.627
0.708 0.446 0.668 0.679 0.663 0.609 0.655
GraphSAGE Acc F1 0.658 0.504 0.634 0.641 0.509 0.506 0.507
0.680 0.649 0.659 0.666 0.652 0.590 0.663
Table 3: Classification performances for ArXiV. The best performances have been indicated in bold while the second best and the third best are underlined and dashed line respectively.
Embedding DeepWalk DGI ContFUSE GRACE Node2Vec Random SGCL VGAE COLES CCA-SSG MVGRL
Runtime (s) 121.69 ± 2.841 8.39 ± 0.221 14.16 ± 0.285 309.25 ± 4.874 118.17 ± 3.009 0.03 ± 0.004 91.05 ± 0.622 95.62 ± 2.440 46.51 ± 0.687 24.12 ± 0.091 9822.58 ± 49.775
Embedding DeepWalk DGI ContFUSE Node2Vec CCA-SSG Random
Table 5: ArXiV.
Runtime (s) 4173.83 125.45 298.66 4051.59 427.22 0.53
Runtimes
for
Table 4: Runtimes across baselines averaged across small to medium sized datasets.
6.3 Ablation Study To assess the contribution of contrastive supervision in Contrastive FUSE, we perform an ablation study by removing the contrastive term and optimizing only the unsupervised modularity objective (i.e., setting λ = 0). The resulting embeddings are evaluated using the same downstream classifiers and evaluation protocols as the full model. Across both medium-scale datasets and the large OGBN-ArXiv graph, the unsupervised variant consistently underperforms the full model, highlighting the importance of contrastive pairwise supervision for learning discriminative node representations. For a detailed quantitative analysis and full results, please refer to Appendix A.1.
6.4 Sensitivity Analysis We conduct a sensitivity analysis to examine the robustness of Contrastive FUSE with respect to its key hyperparameters under varying numbers of contrastive pairs. The 16
proposed adaptive scaling strategy enables effective optimization across datasets of different sizes and graph densities. A detailed breakdown of hyperparameter settings and results is provided in Appendix A.2.
6.5 Scalability Experiments We evaluate the scalability of Contrastive FUSE on large-scale graphs and compare its performance against representative baseline methods. The results show that Contrastive FUSE achieves competitive predictive performance while substantially reducing runtime, demonstrating a favorable trade-off between accuracy and efficiency. These findings indicate that the proposed framework scales effectively to large realworld graphs. Comprehensive scalability results and runtime analyses are reported in Appendix A.4.
6.6 Visualizations Figure 3 illustrates the learning pipeline of Contrastive FUSE. The method constructs two complementary signals in parallel: a structural signal derived from the graph adjacency through the modularity matrix, and a contrastive signal derived from labeled node pairs via a signed contrastive Laplacian. These signals produce corresponding gradients that capture community-level structure and pairwise similarity or dissimilarity, respectively. The gradients are linearly combined and used to update the node embeddings through a gradient ascent step, followed by row-wise normalization to enforce unit-norm constraints. Additionally we have plotted the accuracy and F1 scores averaged across the datasets for small to medium sized datasets along with their runtimes in Fig 1 and Fig 2 respectively which shows the applicability of Contrastive FUSE across various domains.
7 Theoretical Results Theorem 1 (Lipschitz Smoothness of the Contrastive FUSE Objective) Let e − λ Tr(S ⊤ Lc S), J(S) = Tr(S ⊤ BS) e ∈ Rn×n is the (symmetric) modularity matrix of the graph and Lc ∈ Rn×n is the where B symmetric signed contrastive Laplacian. Then the gradient ∇J(S) is Lipschitz continuous with respect to the Frobenius norm. In particular, for all S, S ′ ∈ Rn×k , ∥∇J(S) − ∇J(S ′ )∥F ≤ L ∥S − S ′ ∥F ,
L = 2 ∥B − λLc ∥2 ,
where ∥ · ∥2 denotes the spectral norm. Consequently, J is an L-smooth function.
e and Lc are symmetric matrices. Define Proof We begin by observing that both B e − λLc . M := B The objective function can then be written compactly as J(S) = Tr(S ⊤ M S).
17
(a) Accuracy across classifiers
(b) Macro-F1 across classifiers
Fig. 1: Downstream classification performance of different embedding methods evaluated using Logistic Regression, GAT, GCN, and GraphSAGE. Accuracy (a) and Macro-F1 (b) are reported across all small-to-medium-sized benchmark datasets.
A standard result from matrix calculus states that for any symmetric matrix M , the gradient of Tr(S ⊤ M S) with respect to S is given by ∇S Tr(S ⊤ M S) = 2M S. Applying this identity yields ∇J(S) = 2M S. For any two matrices S, S ′ ∈ Rn×k , the difference of the gradients can therefore be expressed as ∇J(S) − ∇J(S ′ ) = 2M (S − S ′ ).
18
Fig. 2: Runtime comparison across embedding methods on a logarithmic (10k ) scale. ContFUSE achieves strong efficiency while remaining competitive with significantly more expensive baselines.
Input Graph A
Contrastive Pairs (i, j, yij )
(adjacency, degrees)
(+1 same, -1 diff)
Modularity Matrix ⊤ e = A − d1 B 2m
Signed Contrastive Laplacian −1/2
Lc = I − Dc
−1/2
Y Dc
Contrastive Gradient Gcon = −Lc S
Structural Gradient e Gmod = BS
Combine Gradients G = Gmod + λGcon Gradient Ascent Step Se = S + η G Row Normalization (Projection) Sei Si ← e ∥Si ∥2
Final Node Embeddings S
Fig. 3: Learning pipeline of Contrastive FUSE.
19
Taking the Frobenius norm on both sides and using the submultiplicativity of the spectral norm, we obtain ∥∇J(S) − ∇J(S ′ )∥F = 2∥M (S − S ′ )∥F ≤ 2∥M ∥2 ∥S − S ′ ∥F . e − λLc gives Substituting back M = B e − λLc ∥2 ∥S − S ′ ∥F . ∥∇J(S) − ∇J(S ′ )∥F ≤ 2∥B Hence, the gradient of J is Lipschitz continuous with Lipschitz constant L = 2∥B − λLc ∥2 , which establishes the claimed smoothness. □ Theorem 2 (Directional Stability of Modularity Gradients) Let G = (V, E) be an undirected graph with |V | = n, |E| = m, adjacency matrix A, and degree vector d = (d1 , . . . , dn )⊤ . Let S ∈ Rn×k be an embedding matrix with rows Si . Define dd⊤ S d1⊤ S Gtrue = AS − , Gapprox = AS − . 2m 2m Assume: (i) ∥Si ∥2 = 1 for all i; (ii) E[⟨Si , Sj ⟩] = 0 and Var(⟨Si , Sj ⟩) = O(1/k) for i ̸= j; (iii) The second Zagreb index satisfies X
M2 (G) :=
di dj ≥ c
(i,j)∈E
Then
∥d∥42 m
for some constant c > 0.
1 n √ cos(Gtrue , Gapprox ) ≥ 1 − O √ + . m ∥d∥2 m
Proof Subtracting the two gradients gives ∆G = Gtrue − Gapprox =
d(d⊤ S − 1⊤ S) dd⊤ S − d1⊤ S = . 2m 2m
Using ∥uv ⊤ X∥F ≤ ∥u∥2 ∥v ⊤ X∥2 , we obtain 1 ∥d∥2 ∥d⊤ S − 1⊤ S∥2 . 2m
∥∆G∥F ≤
(1)
Since ∥Si ∥2 = 1 for all i, n X
∥1⊤ S∥2 =
i=1
≤
Si 2
n X
∥Si ∥2 = n.
(2)
i=1
Next, expand ∥d⊤ S∥22 =
X
d2i ∥Si ∥22 +
i
X
di dj ⟨Si , Sj ⟩.
i̸=j
The diagonal term equals ∥d∥22 . By isotropy, the cross terms have zero mean and concentrate around zero. Hence, with high probability, ∥d⊤ S∥2 = O(∥d∥2 ).
20
(3)
Combining (2) and (3), ∥d⊤ S − 1⊤ S∥2 ≤ ∥d⊤ S∥2 + ∥1⊤ S∥2 = O(∥d∥2 ) + O(n). Substituting into (1) yields ∥d∥22 ∥∆G∥F = O m
n∥d∥2 +O m
.
(4)
Now consider the dominant structural term AS. A direct expansion gives ∥AS∥2F =
n X
X
⟨Sj , Sℓ ⟩.
i=1 j,ℓ∈N (i)
Under isotropy, off-diagonal contributions cancel in expectation, yielding X dj dℓ = M2 (G). ∥AS∥2F ≳ (j,ℓ)∈E
Thus, ∥AS∥F ≳
p
M2 (G).
(5)
Using ∥Gapprox ∥F ≥ ∥AS∥F and the inequality cos(U, V ) ≥ 1 −
∥U − V ∥F , ∥V ∥F
we obtain cos(Gtrue , Gapprox ) ≥ 1 −
∥∆G∥F . ∥AS∥F
Substituting (4) and (5), n∥d∥ ∥d∥2 p 2 cos(Gtrue , Gapprox ) ≥ 1 − O + p 2 m M2 (G) m M2 (G) By assumption (iii),
! .
p √ m M2 (G) ≳ ∥d∥22 m.
So, 1 n √ cos(Gtrue , Gapprox ) ≥ 1 − O √ + . m ∥d∥2 m This is positive for all sufficiently large m.
□
Theorem 3 (Edge Lower Bound for Effective Zagreb Control) Let G = (V, E) be an undirected graph with |V | = n, |E| = m, degree vector d = (d1 , . . . , dn )⊤ , and second Zagreb index X M2 (G) := di dj . (i,j)∈E
Assume that there exists a constant c > 0 such that ∥d∥42 . m Then a sufficient condition for the error terms M2 (G) ≥ c
∥d∥2 p 2 m M2 (G)
and
21
n∥d∥ p 2 m M2 (G)
(A3)
to be O(m−1/2 ) is m ≥
1 c
1+
n ∥d∥2
2 .
In particular, under this condition the directional cosine bound 1 n √ cos(Gtrue , Gapprox ) ≥ 1 − O √ + m ∥d∥2 m is nonnegative.
Proof Starting from Assumption (A3), M2 (G) ≥ c
∥d∥42 , m
taking square roots yields p
M2 (G) ≥
We first bound the term
√ ∥d∥22 c √ . m
(1)
∥d∥2 p 2 . m M2 (G)
Substituting (1), ∥d∥2 ∥d∥22 1 1 p 2 = √ √ . ≤ √ 2 /√m c m m · c ∥d∥ m M2 (G) 2 Next, consider the second term n∥d∥ p 2 . m M2 (G) Again using (1), n∥d∥ n∥d∥2 n 1 √ . p 2 ≤ √ = √ √ c ∥d∥2 m m · c ∥d∥22 / m m M2 (G) Combining (2) and (3), the total error term satisfies ∥d∥2 n∥d∥ n 1 1 √ + p 2 √ + p 2 ≤ √ . c m ∥d∥2 m m M2 (G) m M2 (G)
(2)
(3)
(4)
For the right-hand side of (4) to be at most 1, it suffices that √ 1 n √ ≤ c. 1+ ∥d∥2 m Rearranging yields the stated condition m ≥
1 c
1+
n ∥d∥2
2 .
Under this condition, the cosine lower bound remains nonnegative, completing the proof. □ Remark 1 (Empirical Validation of the Zagreb Assumption and Edge Bound) We empirically evaluate the normalized Zagreb constant M2 (G) m c(G) = ∥d∥42
22
Dataset Cora CiteSeer PubMed WikiCS Amazon-Photo OGBN-ArXiv
n 2,708 3,327 19,717 11,701 7,650 169,343
m 5,278 4,552 44,324 216,123 119,081 1,157,799
∥d∥2 2
3.39 × 10 2.51 × 102 1.22 × 103 8.62 × 103 4.95 × 103 2.88 × 104
c(G)
mmin
0.176 0.285 0.235 0.180 0.216 0.049
459.3 714.9 1252.6 30.9 30.0 971.9
Table 6: Edge bounds for different datasets used in the experiments.
and the degree norm ∥d∥2 for several standard benchmark graphs. The results are summarized in Table 6. Across all datasets, the constant c(G) is bounded away from zero, with values ranging from approximately 0.05 to 0.29. Moreover, all graphs satisfy ∥d∥2 ≫ n, indicating substantial degree heterogeneity. Substituting these values into the sufficient edge condition from Theorem 3, m ≥
1 c(G)
1+
n ∥d∥2
2 ,
we find that the required number of edges (mmin ) is at most on the order of tens to hundreds, whereas the actual graphs contain between 103 and 106 edges (Table 6). Consequently, all benchmark datasets lie well within the regime where directional stability of the modularity gradient approximation is guaranteed. These results confirm that Assumption (iii) is not restrictive in practice and is satisfied with a wide margin by real-world graphs.
8 Discussion and Conclusion 8.1 Time Complexity Analysis. We analyze the computational complexity of Contrastive FUSE per optimization iteration and over the full training procedure. Let n = |V | be the number of nodes, |E| the number of edges, P the number of labeled contrastive pairs, and k the embedding dimension. e , where B e = The structural (modularity) gradient is computed as Gmod = BS d1⊤ A − 2m . Since A is sparse with |E| nonzero entries, the matrix–vector multiplication AS requires O(|E|k ) time. The degree-correction term involves a rank-one operation and costs O(nk ), which is dominated by the adjacency multiplication in sparse graphs. Consequently, the overall cost of computing Gmod is O(|E|k ) per iteration. −1/2 −1/2 The contrastive gradient is given by Gcon = −Lc S , where Lc = I − Dc Y Dc is the signed contrastive Laplacian. The matrix Y is sparse and contains exactly P nonzero entries corresponding to the labeled node pairs. Multiplying Y with S −1/2 therefore requires O(P k ) time, and the diagonal scaling by Dc incurs only O(nk ) overhead. As a result, the contrastive term contributes O(P k ) time per iteration. 23
After the gradient update, row-wise normalization of the embedding matrix S requires computing the ℓ2 norm of each row and rescaling, which costs O(nk ) per iteration. Combining all components, the per-iteration time complexity of Contrastive FUSE is
O((|E| + P )k ), where the normalization term is lower order for sparse graphs. Over T iterations, the total training complexity becomes
O(T (|E| + P )k ).
8.2 Conclusion. In summary, Contrastive FUSE provides a simple yet effective framework for contrastive graph representation learning that unifies modularity-based structural modeling with pairwise supervision in a scalable spectral formulation. While the method demonstrates strong and consistent performance across diverse benchmarks and real-world networks ranging from knowledge graphs to a biological database, its effectiveness naturally depends on the availability and quality of labeled node pairs, with performance improving as the number of pairwise constraints increases. Additionally, learning on dense graphs requires careful scaling of the learning rate and contrastive weight to ensure stable optimization, as reflected in our adaptive parameter strategy. Despite these limitations, the framework offers substantial flexibility and computational efficiency, making it well-suited for large-scale applications. Future work will focus on identifying and curating additional biological datasets where pairwise supervision is intrinsic, such as genetic interaction and drug–target networks, as well as extending Contrastive FUSE to multi-view and heterogeneous graph settings and try to put forward an efficient method for dealing with datasets under a contrastive scenario.
9 Reproducibility The results of the experiments can be exactly reproduced from the codes given in https: //github.com/SujanChakraborty/Contrastive FUSE. The python environment along with the notebooks have been provided. Along with these, the required specifications in python can be found inside requirements.txt. A detailed guide has been provided in README.md regarding running the codes step by step.
References [1] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’14), pp. 701–710. ACM, New York City, NY, USA (2014). https://doi.org/10.1145/2623330.2623732 24
[2] Grover, A., Leskovec, J.: node2vec: Scalable Feature Learning for Networks (2016). https://arxiv.org/abs/1607.00653 [3] Kipf, T.N., Welling, M.: Variational Graph Auto-Encoders (2016). https://arxiv. org/abs/1611.07308 [4] Veličković, P., Fedus, W., Hamilton, W.L., Liò, P., Bengio, Y., Hjelm, R.D.: Deep Graph Infomax (2018). https://arxiv.org/abs/1809.10341 [5] Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., Wang, L.: Deep Graph Contrastive Representation Learning (2020). https://arxiv.org/abs/2006.04131 [6] Shu, L., Du, E., Chang, Y., Chen, C., Zheng, Z., Xing, X., Shen, S.: Sgcl: Contrastive representation learning for signed graphs. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. CIKM ’21, pp. 1671–1680. Association for Computing Machinery, New York, NY, USA (2021). https://doi.org/10.1145/3459637.3482478 . https://doi.org/10.1145/3459637.3482478 [7] Etzion, H., Moshe, U.: Multi-view Graph Feature Propagation for Privacy Preservation and Feature Sparsity (2025). https://arxiv.org/abs/2510.11347 [8] Chen, S., Wang, H., Zhang, Y., Li, J.: Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning (2025). https://arxiv.org/abs/ 2507.11732 [9] Xiao, Z., Deng, Y.: Graph embedding-based novel protein interaction prediction via higher-order graph convolutional network 15(9), 1–18 (2020) [10] Yuan, J., Li, J., Sun, R., Yang, Y.: Embeddti: Enhancing molecular representations via sequence embedding and graph convolutional networks for drug–target interaction prediction. Biomolecules 11(12), 1783 (2021) https://doi.org/10. 3390/biom11121783 [11] Cao, T., Xu, Q., Yang, Z., Huang, Q.: Practically unbiased pairwise loss for recommendation with implicit feedback. IEEE Transactions on Pattern Analysis and Machine Intelligence (2024) https://doi.org/10.1109/TPAMI.2024.3519711 [12] Sidana, S., Trofimov, M., Horodnytskyi, O., Laclau, C., Maximov, Y., Amini, M.R.: User preference and embedding learning with implicit feedback for recommender systems. Data Mining and Knowledge Discovery (2022) [13] Mercado, P., Tudisco, F., Hein, M.: Spectral Clustering of Signed Graphs via Matrix Power Means (2019). https://arxiv.org/abs/1905.06230 [14] Newman, M.E.J.: Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103(23), 8577–8582 (2006)
25
[15] Tsitsulin, A., Palowitch, J., Perozzi, B., Müller, E.: Graph clustering with graph neural networks. Journal of Machine Learning Research (JMLR) 24(1), 1–21 (2023) [16] Bhowmick, A., Kosan, M., Huang, Z., et al.: Dgcluster: A neural framework for attributed graph clustering via modularity maximization. Proceedings of the AAAI Conference on Artificial Intelligence 38(10), 11069–11077 (2024) [17] You, Y., Chen, T., Sui, Y., Chen, T., Wang, Z., Shen, Y.: Graph Contrastive Learning with Augmentations (2021). https://arxiv.org/abs/2010.13902 [18] Zhu, H., Sun, K., Koniusz, P.: Contrastive Laplacian Eigenmaps (2022). https: //arxiv.org/abs/2201.05493 [19] Bo, D., Shi, C., Wang, L., Liao, R.: Specformer: Spectral Graph Neural Networks Meet Transformers (2023). https://arxiv.org/abs/2303.01028 [20] Liu, N., Wang, X., Bo, D., Shi, C., Pei, J.: Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum (2022). https://arxiv.org/abs/2210. 02330 [21] Zhang, T., et al.: From canonical correlation analysis to self-supervised graph neural networks. In: Advances in Neural Information Processing Systems (NeurIPS) (2021) [22] Hassani, K., Ahmadi, A.H.: Contrastive Multi-View Representation Learning on Graphs (2020). https://arxiv.org/abs/2006.05582 [23] Cucuringu, M., Koutis, I., Chawla, S., Miller, G., Peng, R.: Scalable Constrained Clustering: A Generalized Spectral Method (2016). https://arxiv.org/abs/1601. 04746 [24] Derr, T., Ma, Y., Tang, J.: Signed Graph Convolutional Network (2018). https: //arxiv.org/abs/1808.06354 [25] Zhang, Z., Liu, J., Zhao, K., Yang, S., Zheng, X., Wang, Y.: Contrastive learning for signed bipartite graphs. In: Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR ’23, pp. 1629–1638. Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3539618.3591655 . https://doi.org/10.1145/3539618.3591655 [26] Qi, Y., Du, E., Shu, L., Chen, C.: Sgca: Signed graph contrastive learning with adaptive augmentation. In: Proceedings of the 2024 International Joint Conference on Neural Networks (IJCNN), pp. 1–10. IEEE, Yokohama, Japan (2024). https://doi.org/10.1109/IJCNN60899.2024.10651025
26
[27] Li, Y., et al.: Signed laplacian graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence 37, 4452–4460 (2023) [28] McCallum, A., Nigam, K., Rennie, J., Seymore, K.: Automating the construction of internet portals with machine learning. Information Retrieval 3(2), 127–163 (2000) https://doi.org/10.1023/A:1009953814988 [29] Giles, C.L., Bollacker, K.D., Lawrence, S.: Citeseer: an automatic citation indexing system. In: Proceedings of the Third ACM Conference on Digital Libraries. DL ’98, pp. 89–98. Association for Computing Machinery, New York, NY, USA (1998). https://doi.org/10.1145/276675.276685 . https://doi.org/10.1145/276675.276685 [30] Namata, G.M., London, B., Getoor, L., Huang, B.: Query-driven active surveying for collective classification. In: Proceedings of the Workshop on Mining and Learning with Graphs (MLG). ACM, Beijing, China (2012). http://linqs.cs.umd.edu/basilic/web/Publications/2012/namata:mlg12wkshp/namata-mlg12.pdf [31] Mernyei, P., Cangea, C.: Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks (2022). https://arxiv.org/abs/2007.02901 [32] McAuley, J., Targett, C., Shi, Q., Hengel, A.: Image-based Recommendations on Styles and Substitutes (2015). https://arxiv.org/abs/1506.04757 [33] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J.: Open Graph Benchmark: Datasets for Machine Learning on Graphs (2021). https://arxiv.org/abs/2005.00687 [34] Kipf, T.N., Welling, M.: Semi-Supervised Classification with Graph Convolutional Networks (2017). https://arxiv.org/abs/1609.02907 [35] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph Attention Networks (2018). https://arxiv.org/abs/1710.10903 [36] Hamilton, W.L., Ying, R., Leskovec, J.: Inductive Representation Learning on Large Graphs (2018). https://arxiv.org/abs/1706.02216
A Additional Experiments A.1 Ablation Study To assess the contribution of contrastive supervision in the proposed framework, we conduct an ablation study in which the contrastive term is removed and embeddings are learned solely by optimizing the unsupervised modularity objective. Specifically, 27
Classifier Logistic GAT GCN GraphSAGE Runtime (s)
Acc
F1
0.502 ± 0.017 0.681 ± 0.008 0.677 ± 0.006 0.678 ± 0.008
0.486 ± 0.064 0.724 ± 0.007 0.717 ± 0.007 0.722 ± 0.009
8.3278 ± 0.1237
Classifier
Acc
F1
Logistic GAT GCN GraphSAGE
0.4934 0.5863 0.5862 0.5409
0.4896 0.6359 0.6265 0.6221
Runtime (s)
Table 7: Results for the unsupervised modularity gradient on the datasets except ArXiV.
217.2101
Table 8: Results for the unsupervised modularity gradient on ArXiV.
we set λ = 0 and evaluate the resulting embeddings using the same downstream classifiers and evaluation protocol as in the full model. Table 7 reports results averaged across all datasets except OGBN-ArXiv. While the unsupervised modularity objective is able to capture coarse community structure, its performance consistently lags behind the full Contrastive FUSE model across all classifiers. When coupled with expressive GNN classifiers such as GAT, GCN, and GraphSAGE, the absence of pairwise supervision results in lower classification performance compared to the contrastive variant. The performance degradation is more pronounced on the large-scale OGBN-ArXiv dataset, as shown in Table 8. In this setting, removing contrastive supervision leads to a substantial drop in accuracy and macro-F1 across all classifiers. This highlights the limitation of purely modularity- based objectives in dense and heterogeneous graphs, where community structure alone does not sufficiently reflect semantic similarity between nodes. In addition to reduced predictive performance, the unsupervised variant exhibits inferior scalability characteristics. Although the per-iteration runtime is lower due to the absence of contrastive gradient computations, the overall embedding quality deteriorates significantly, especially on large graphs. Overall, the ablation results confirm that contrastive pairwise supervision is a key component of Contrastive FUSE. By explicitly enforcing attraction and repulsion between labeled node pairs, the contrastive term refines community-level representations into discriminative embeddings, yielding substantial improvements in downstream classification performance across both medium- and large-scale graphs.
A.2 Sensitivity Analysis Table 9 (a)–(c) analyzes the sensitivity of Contrastive FUSE to its key hyperparameters under varying numbers of contrastive pairs. Across datasets, the method demonstrates stable performance over a broad range of settings, indicating that it is not overly sensitive to precise hyperparameter tuning. The scaled learning rate ηscaled adapts naturally to dataset size and graph density, with larger graphs such as OGBN-ArXiv requiring higher values to maintain effective optimization. The contrastive weight λscaled plays a central role in balancing structural and pairwise signals the preferred values being near to 1 for medium sized datasets while values near 0.5 28
Dataset Cora CiteSeer PubMed WikiCS Amazon Photo ArXiV
k 150 120 200 180 200 160
ηscaled
λscaled
T
Acc (%)
F1
Time (s)
0.86 0.99 0.95 0.99 0.84 0.28
100 300 100 200 300 300
84.13 72.80 78.85 71.51 82.13 68.24
0.843 0.713 0.778 0.730 0.834 0.699
1.49 3.96 16.38 21.48 21.17 439.13
4
10 104 105 105 105 107
(a) 50,000 contrastive pairs Dataset
k
ηscaled
λscaled
T
Acc (%)
F1
Time (s)
Cora CiteSeer PubMed WikiCS Amazon Photo ArXiV
180 130 170 170 170 170
103 104 105 105 105 107
0.80 0.48 0.91 0.38 0.99 0.27
300 300 200 100 200 200
85.46 73.27 79.61 74.77 81.57 67.16
0.851 0.718 0.789 0.752 0.828 0.686
5.84 5.07 28.06 10.55 12.49 316.45
(b) 100,000 contrastive pairs Dataset
k
ηscaled
λscaled
T
Acc (%)
F1
Time (s)
Cora CiteSeer PubMed WikiCS Amazon Photo ArXiV
170 190 130 180 190 180
103 104 105 105 104 106
0.94 0.92 0.92 0.41 0.95 0.91
300 100 200 100 200 300
85.52 73.30 79.38 75.03 81.84 70.70
0.853 0.707 0.787 0.751 0.829 0.711
9.81 4.21 25.49 14.45 18.95 520.55
(c) 500,000 contrastive pairs
Table 9: Sensitivity analysis of Contrastive FUSE under varying numbers of contrastive pairs. It can be noticed that higher ηscaled enhances the performance for larger datasets.
are preferable for larger sized datasets. Overall, the results confirm that the proposed adaptive scaling strategy enables robust and effective learning across diverse graph regimes.
A.3 Noise Sensitivity Study We conducted a noise sensitivity study on the Cora dataset (results can be found in Tables 10, 11, 12) by randomly flipping a fraction of pairwise labels (positive ↔ negative). Importantly, noise is introduced only in the training pairs, while evaluation is performed on clean test pairs, ensuring that we measure robustness of the learned embeddings rather than robustness at inference time. Across 50K and 100K contrastive pairs, all methods exhibit a gradual degradation in performance as the noise level increases from 0% to 40%, indicating stability rather than catastrophic failure. Contrastive FUSE remains competitive under moderate noise (≤ 20%), with only a small drop in accuracy (approximately 1–2%), demonstrating robustness of 29
the modularity-driven objective even with corrupted supervision. Increasing the number of pairs from 50K to 100K improves robustness across all methods. In particular, Contrastive FUSE exhibits more stable performance across noise levels at 100K, suggesting a noise-averaging effect where the influence of corrupted labels diminishes with larger training sets. Further, the results for Contrastive FUSE on the Arxiv dataset have been reported in Table 13, all the results being reported with the GCN classifier. Overall, Contrastive FUSE demonstrates strong robustness to moderate label noise, maintaining high accuracy even with 20% corrupted pairs. We will include these results and discussion in the revised manuscript, along with additional results for larger-scale settings (500K pairs). Method
0.00
0.05
0.10
0.20
0.30
0.40
DeepWalk ContFUSE Node2Vec
0.8235 0.8207 0.8088
0.8235 0.8159 0.8053
0.8159 0.8043 0.7946
0.8145 0.7903 0.7915
0.7873 0.7389 0.7503
0.7164 0.7046 0.6347
Table 10: Noise sensitivity (50K pairs): Accuracy vs. label flip fraction.
Method
0.00
0.05
0.10
0.20
0.30
0.40
DeepWalk ContFUSE Node2Vec
0.8202 0.8209 0.8137
0.8216 0.8196 0.8157
0.8220 0.8160 0.8164
0.8168 0.8030 0.8082
0.8009 0.7671 0.7718
0.7468 0.7004 0.6481
Table 11: Noise sensitivity (100K pairs): Accuracy vs. label flip fraction.
Method
0.00
0.05
0.10
0.20
0.30
0.40
DeepWalk ContFUSE Node2Vec
0.8189 0.8206 0.8118
0.8193 0.8196 0.8165
0.8193 0.8163 0.8169
0.8173 0.8084 0.8157
0.8102 0.7874 0.8011
0.7837 0.7320 0.7174
Table 12: Noise sensitivity (500K pairs): Accuracy vs. label flip fraction.
A.4 Scalability Experiments We performed an experiment on a large dataset, namely the OGBN-Products which is an undirected and unweighted graph. A sensitivity analysis on the Products dataset 30
Pairs
Metric
0.00
0.05
0.10
0.20
0.30
0.40
50K
Acc F1
0.5862 0.6184
0.5864 0.6213
0.5851 0.6172
0.5804 0.6103
0.5717 0.6179
0.5692 0.6137
100K
Acc F1
0.5950 0.6189
0.5908 0.6197
0.5874 0.6099
0.5823 0.6145
0.5816 0.6208
0.5719 0.6212
500K
Acc F1
0.6042 0.6185
0.6009 0.6153
0.5988 0.6131
0.5915 0.6135
0.5859 0.6044
0.5794 0.6065
Table 13: Noise sensitivity of Contrastive FUSE for Arxiv across training pairs. For each pair setting, the first row reports Accuracy and the second row reports F1 score (GCN classifier).
for 100,000 pairs under GCN showed that for k = 130, ηscaled = 107 , λscaled = 0.145 and 200 iterations, the accuracy and f1 values were 0.699 and 0.731 respectively. Results for other baselines like DeepWalk (a lighter version of 5 walk length and 10 walks), Random and Given can be found in Table 14. While DeepWalk takes 78,353.47 seconds (approx 22 hours) to run, while the optimized version of Contrastive FUSE takes only 8503.53 (approx 2.36 hours) to run, making it nearly 9 times faster with approximately a compromise of 5-6 percent in accuracy and 3-4 percent in F1 scores’ performance. We compare against GCN variant only because it is a fast an efficient GNN to use for large graph datasets. It can be seen that Contrastive FUSE can be a suitable alternative to the best performing baseline DeepWalk considering both the performance (a 4-5 percent drop approx.) and runtimes (almost 4 times faster) which makes this algorithm scalable as well as well suited to apply in large real world datasets.
Model Logistic GAT GCN GraphSAGE
DeepWalk
Random
Given
Acc.
F1
Acc.
F1
Acc.
F1
0.506 0.747 0.758 0.747
0.479 0.769 0.771 0.758
0.504 0.526 0.546 0.521
0.488 0.671 0.645 0.596
0.494 0.585 0.644 0.631
0.488 0.643 0.658 0.662
Table 14: Performance comparison (Accuracy / F1) for OGBN-Products across different embedding initializations using 100,000 training pairs.
A.5 Exact vs Approximate Modularity Gradient We conducted a direct comparison between the exact modularity gradient (based on the dense dd⊤ formulation) and our proposed sparse approximation (using degreescaled aggregation) on the Cora dataset across multiple pair regimes. 31
Pairs
Method
Accuracy
F1
Runtime (s)
Speedup
50K
Exact Approx
0.8055 0.8041
0.8064 0.8050
149.52 3.98
37.6×
100K
Exact Approx
0.7986 0.8003
0.7966 0.7984
150.49 3.81
39.5×
500K
Exact Approx
0.7998 0.8009
0.7979 0.7993
152.89 6.64
23.2×
Table 15: Exact vs. Approximate Modularity Gradient: Speed–Quality Trade-off on Cora.
Pairs
Metric
Results
Runtime (s)
50K
Acc F1
0.6450 0.6751
302.6286
100K
Acc F1
0.6611 0.6796
302.0929
500K
Acc F1
0.6712 0.6849
320.3705
Table 16: Approximated modularity gradient results on Arxiv with GCN classifier
As shown in Table 15, both variants achieve nearly identical performance across all settings. The difference in accuracy and F1 scores remains within ∼0.2–0.3%, indicating that the approximation preserves the optimization objective effectively. To further validate the approximation, we compute the cosine similarity between the exact and approximate gradients at initialization, obtaining a very high alignment of 0.995. This confirms that both gradients point in nearly identical directions, explaining the negligible performance gap. The approximate method yields a substantial speedup of 23×–40× compared to the exact computation. Further, applying the same setting on the Arxiv dataset, the exact version of modularity gradient faced a memory error while the results for the approximate gradient are reported in Table 16. This is expected since the exact gradient requires forming and multiplying with a dense n × n matrix, whereas the approximation operates in O(m) time using sparse operations. These results demonstrate a clear speed–quality trade-off: the proposed approximation achieves comparable performance to the exact formulation while being orders of magnitude faster, making it suitable for medium- and large-scale graphs.
A.6 Embedding Isolation Study To explicitly disentangle the contribution of the learned embeddings from downstream GNN refinement, we conducted an embedding isolation study (on Cora, results of 32
which can be found in Tables 17, 18, 19 and Arxiv, results of which can be found in Table 20) with three evaluation tiers:
• Tier 1: Linear probe (logistic regression on concatenated embeddings), which evaluates pure embedding quality without any graph structure or learned message passing. • Tier 2: MLP probe, which introduces a non-linear readout but still does not use graph structure. • Tier 3: GNN-on-top (GCN, GAT, GraphSAGE), which leverages full graph structure and quantifies the additional gains from message passing.
Method
GAT
GCN
GraphSAGE
Logistic
MLP
DeepWalk ContFUSE Node2Vec
0.8268 0.8230 0.8107
0.8235 0.8207 0.8088
0.8429 0.7982 0.8306
0.4814 0.5103 0.5030
0.8043 0.7906 0.7970
Table 17: Embedding isolation study (Cora, 50K pairs). Accuracy across classifier tiers.
Method
GAT
GCN
GraphSAGE
Logistic
MLP
DeepWalk ContFUSE Node2Vec
0.8285 0.8166 0.8149
0.8200 0.8209 0.8137
0.8395 0.8314 0.8229
0.4974 0.5026 0.4982
0.8243 0.7800 0.8240
Table 18: Embedding isolation study (Cora, 100K pairs). Accuracy across classifier tiers.
Method
GAT
GCN
GraphSAGE
Logistic
MLP
DeepWalk ContFUSE Node2Vec
0.8309 0.8206 0.8200
0.8187 0.8205 0.8117
0.8392 0.8298 0.8246
0.4936 0.5017 0.5025
0.8203 0.7661 0.8289
Table 19: Embedding isolation study (Cora, 500K pairs). Accuracy across classifier tiers.
Under the linear probe setting, FUSE consistently achieves the highest accuracy across both 50K and 100K pair settings (e.g., 0.5103 vs. 0.4814 for DeepWalk at 33
Pairs
Metric
GAT
GCN
GraphSAGE
Logistic
MLP
50K
Acc F1
0.5851 0.6238
0.5862 0.6184
0.5779 0.6591
0.4896 0.5560
0.5958 0.5745
100K
Acc F1
0.5937 0.6189
0.5950 0.6195
0.5781 0.5980
0.5023 0.5682
0.5774 0.5779
500K
Acc F1
0.6062 0.6371
0.6042 0.6186
0.6027 0.6614
0.5014 0.5673
0.6080 0.5230
Table 20: Embedding isolation study of Contrastive FUSE for Arxiv across training pairs. For each pair setting, the first row reports Accuracy and the second row reports F1 score.
50K), demonstrating that the learned embeddings themselves are more discriminative. This isolates and confirms the effectiveness of the proposed objective independent of any GNN refinement. With an MLP probe, all methods improve substantially, indicating that embeddings encode useful non-linear structure. FUSE remains competitive, though the performance gap narrows as the readout becomes more expressive. When GNNs are applied on top of the embeddings, all methods benefit from additional graph structure. In this setting, the performance differences across embeddings become smaller, suggesting that GNN refinement partially compensates for weaker embeddings. Notably, FUSE remains competitive with strong baselines across all GNN variants. These results clearly separate the contributions: (i) FUSE improves intrinsic embedding quality (as shown by linear probe gains), and (ii) downstream GNN refinement provides an additional, orthogonal boost that benefits all methods.
34