pith. sign in

arxiv: 2605.19916 · v1 · pith:AK26M2TPnew · submitted 2026-05-19 · 💻 cs.LG · cs.AI

Fast and Featureless Node Representation Learning with Partial Pairwise Supervision

Sujan Chakraborty , Saptarshi Bej This is my paper

Pith reviewed 2026-05-20 06:35 UTC · model grok-4.3

classification 💻 cs.LG cs.AI
keywords node representation learningcontrastive learningmodularity approximationpairwise supervisionfeatureless graphsscalable graph methodscommunity structure
0
0 comments X

The pith

Contrastive FUSE learns node representations from partial pairwise labels alone by combining spectral contrastive loss with a fast modularity approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Contrastive FUSE as a framework for node representation learning on graphs that have only partial pairwise node labels and no node features at all. It directly optimizes a spectral contrastive objective that folds community structure signals into the loss via signed pairwise constraints. To make this practical on large graphs, the method substitutes a lightweight approximation for the full modularity gradient, which still drives structure-seeking behavior but allows cheap iterative updates with natural gradient decomposition and adaptive step sizes. A sympathetic reader would care because many real graphs lack reliable features or complete labels, so a method that scales to million-edge networks while matching or beating feature-dependent baselines could change how practitioners handle sparse-supervision settings.

Core claim

Contrastive FUSE directly optimizes a spectral contrastive objective that integrates community-aware structural signals with signed pairwise constraints. Replacing the expensive modularity gradient with a lightweight approximation preserves the structure-seeking behavior while enabling an efficient optimization scheme that uses natural gradient decomposition and adaptive learning-rate scaling for fast updates even on million-edge graphs.

What carries the argument

Lightweight approximation to the modularity gradient, which supplies community structure to the contrastive objective at low cost and supports gradient decomposition.

If this is right

  • Training becomes feasible on graphs with millions of edges without node features.
  • Classification performance matches or exceeds existing contrastive methods that rely on features.
  • Runtime improves substantially over baselines that use full modularity or feature-heavy models.
  • Signed pairwise constraints integrate cleanly with approximated structural signals.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same approximation trick might speed up other spectral objectives in graph clustering.
  • Featureless contrastive learning could extend to dynamic or streaming graphs where features arrive late or never.
  • Partial pairwise supervision paired with modularity signals may improve robustness when labels are noisy.

Load-bearing premise

The lightweight approximation to the modularity gradient keeps the essential structure-seeking behavior of full modularity optimization.

What would settle it

Train Contrastive FUSE and a full-modularity baseline on the same million-edge graph with identical partial labels; if the approximation version shows negligible runtime savings or markedly worse classification accuracy, the central efficiency and performance claims would not hold.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces Contrastive FUSE, a scalable framework for node representation learning on graphs that have partial pairwise node labels but no node features. It directly optimizes a spectral contrastive objective that fuses community-aware structural signals (via modularity) with signed pairwise constraints. For efficiency on large graphs, the expensive modularity gradient is replaced by a lightweight approximation that includes natural gradient decomposition and adaptive learning-rate scaling. Experiments on citation networks, co-purchase graphs, and OGB datasets are reported to show competitive or superior contrastive classification performance together with substantial runtime gains over baselines.

Significance. If the central claims hold, the work would offer a practical route to featureless, community-aware node embeddings under partial supervision, with clear efficiency advantages for million-edge graphs. The combination of modularity-inspired structure with contrastive objectives under signed constraints is a plausible direction for settings where node attributes are absent or unreliable.

major comments (2)
  1. [§4.1] §4.1 (lightweight modularity gradient approximation): the manuscript supplies neither theoretical approximation-error bounds (e.g., deviation from the true modularity matrix or leading eigenvector) nor controlled ablations that disable the approximation and quantify degradation in contrastive classification accuracy or community-recovery metrics. This is load-bearing for the claim that the approximation “preserves the structure-seeking behavior of modularity” while still allowing effective integration with the spectral contrastive objective under partial pairwise supervision.
  2. [§5] §5 (experimental results): the reported performance and runtime gains are asserted without accompanying quantitative tables, standard deviations, or statistical significance tests in the provided description; this prevents verification that the observed advantages are robust across sparse or heterophilic graphs where the approximation bias noted in the skeptic’s stress-test could be most pronounced.
minor comments (2)
  1. [§3] Notation for the signed pairwise constraints and the adaptive scaling factor should be introduced earlier and used consistently throughout the optimization derivation.
  2. [Abstract / §1] The abstract and introduction would benefit from a single sentence clarifying how the partial pairwise labels are converted into the signed constraints used in the contrastive loss.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for their constructive and detailed feedback, which has identified key areas where the manuscript can be strengthened. We address each major comment below and describe the revisions we intend to incorporate.

read point-by-point responses

  1. Referee: [§4.1] §4.1 (lightweight modularity gradient approximation): the manuscript supplies neither theoretical approximation-error bounds (e.g., deviation from the true modularity matrix or leading eigenvector) nor controlled ablations that disable the approximation and quantify degradation in contrastive classification accuracy or community-recovery metrics. This is load-bearing for the claim that the approximation “preserves the structure-seeking behavior of modularity” while still allowing effective integration with the spectral contrastive objective under partial pairwise supervision.

    Authors: We agree that controlled ablations are essential to empirically substantiate the approximation's effectiveness. In the revised manuscript we will add experiments that disable the lightweight approximation (reverting to the full modularity gradient where feasible) and report the resulting changes in contrastive classification accuracy as well as community-recovery metrics such as modularity score and NMI. Regarding theoretical approximation-error bounds, the composite objective combining the spectral contrastive loss with partial signed constraints makes derivation of tight, non-vacuous bounds on deviation from the true modularity matrix or its leading eigenvector technically challenging; we are actively investigating this but currently lack complete results. revision: partial

  2. Referee: [§5] §5 (experimental results): the reported performance and runtime gains are asserted without accompanying quantitative tables, standard deviations, or statistical significance tests in the provided description; this prevents verification that the observed advantages are robust across sparse or heterophilic graphs where the approximation bias noted in the skeptic’s stress-test could be most pronounced.

    Authors: The full manuscript already contains quantitative tables summarizing performance and runtime across citation networks, co-purchase graphs, and OGB datasets. To address the concern, we will augment these tables with standard deviations over multiple independent runs and include statistical significance tests (paired t-tests or Wilcoxon signed-rank tests) comparing Contrastive FUSE against baselines. We will also add targeted experiments or analysis on sparse and heterophilic graph regimes to verify robustness where approximation bias could be more evident. revision: yes

standing simulated objections not resolved
  • Theoretical approximation-error bounds for the lightweight modularity gradient approximation

Circularity Check

0 steps flagged

No circularity: Contrastive FUSE derivation is self-contained with independent approximation and external validation

full rationale

The paper introduces a spectral contrastive objective that couples modularity-inspired structural signals with signed pairwise constraints, then replaces the full modularity gradient with a lightweight approximation justified by computational efficiency and a claimed preservation of structure-seeking behavior. This approximation is presented as a design choice enabling natural gradient decomposition and adaptive scaling, not as a quantity defined in terms of the final learned representations or fitted directly to the contrastive loss. Experiments on citation networks, co-purchase graphs, and OGB datasets supply external benchmarks that are independent of the internal construction. No equations reduce the claimed performance advantage to a tautology, no self-citation chain carries the central uniqueness claim, and the approximation is not renamed as a prediction. The derivation therefore remains non-circular and self-contained against external data.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The lightweight approximation is treated as a modeling choice whose validity is asserted rather than derived.

pith-pipeline@v0.9.0 · 5690 in / 1092 out tokens · 45793 ms · 2026-05-20T06:35:11.180154+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · 9 internal anchors

  1. [1]

    In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’14), pp

    Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social repre- sentations. 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

    work page doi:10.1145/2623330.2623732 2014

  2. [2]

    node2vec: Scalable Feature Learning for Networks

    Grover, A., Leskovec, J.: node2vec: Scalable Feature Learning for Networks (2016). https://arxiv.org/abs/1607.00653

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  3. [3]

    Variational Graph Auto-Encoders

    Kipf, T.N., Welling, M.: Variational Graph Auto-Encoders (2016). https://arxiv. org/abs/1611.07308

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  4. [4]

    Deep Graph Infomax

    Veliˇ ckovi´ c, P., Fedus, W., Hamilton, W.L., Li` o, P., Bengio, Y., Hjelm, R.D.: Deep Graph Infomax (2018). https://arxiv.org/abs/1809.10341

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  5. [5]

    Deep graph contrastive representation learning.arXiv preprint arXiv:2006.04131, 2020

    Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., Wang, L.: Deep Graph Contrastive Representation Learning (2020). https://arxiv.org/abs/2006.04131

    work page arXiv 2020

  6. [6]

    In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

    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 Machin- ery, New York, NY, USA (2021). https://doi.org/10.1145/3459637.3482478 ....

    work page doi:10.1145/3459637.3482478 2021

  7. [7]

    https://arxiv.org/abs/2510.11347

    Etzion, H., Moshe, U.: Multi-view Graph Feature Propagation for Privacy Preservation and Feature Sparsity (2025). https://arxiv.org/abs/2510.11347

    work page arXiv 2025

  8. [8]

    https://arxiv.org/abs/ 2507.11732

    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

    work page arXiv 2025

  9. [9]

    Xiao, Z., Deng, Y.: Graph embedding-based novel protein interaction prediction via higher-order graph convolutional network15(9), 1–18 (2020)

    work page 2020

  10. [10]

    Biomolecules11(12), 1783 (2021) https://doi.org/10

    Yuan, J., Li, J., Sun, R., Yang, Y.: Embeddti: Enhancing molecular representa- tions via sequence embedding and graph convolutional networks for drug–target interaction prediction. Biomolecules11(12), 1783 (2021) https://doi.org/10. 3390/biom11121783

    work page 2021

  11. [11]

    IEEE Transactions on Pattern Analysis and Machine Intelligence (2024) https://doi.org/10.1109/TPAMI.2024.3519711

    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

    work page doi:10.1109/tpami.2024.3519711 2024

  12. [12]

    Data Mining and Knowledge Discovery (2022)

    Sidana, S., Trofimov, M., Horodnytskyi, O., Laclau, C., Maximov, Y., Amini, M.R.: User preference and embedding learning with implicit feedback for recom- mender systems. Data Mining and Knowledge Discovery (2022)

    work page 2022

  13. [13]

    Spectral Clustering of Signed Graphs via Matrix Power Means

    Mercado, P., Tudisco, F., Hein, M.: Spectral Clustering of Signed Graphs via Matrix Power Means (2019). https://arxiv.org/abs/1905.06230

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  14. [14]

    Proceedings of the National Academy of Sciences103(23), 8577–8582 (2006) 25

    Newman, M.E.J.: Modularity and community structure in networks. Proceedings of the National Academy of Sciences103(23), 8577–8582 (2006) 25

    work page 2006

  15. [15]

    Journal of Machine Learning Research (JMLR)24(1), 1–21 (2023)

    Tsitsulin, A., Palowitch, J., Perozzi, B., M¨ uller, E.: Graph clustering with graph neural networks. Journal of Machine Learning Research (JMLR)24(1), 1–21 (2023)

    work page 2023

  16. [16]

    Proceedings of the AAAI Conference on Artificial Intelligence38(10), 11069–11077 (2024)

    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 Intelligence38(10), 11069–11077 (2024)

    work page 2024

  17. [17]

    https://arxiv.org/abs/2010.13902

    You, Y., Chen, T., Sui, Y., Chen, T., Wang, Z., Shen, Y.: Graph Contrastive Learning with Augmentations (2021). https://arxiv.org/abs/2010.13902

    work page arXiv 2021

  18. [18]

    https: //arxiv.org/abs/2201.05493

    Zhu, H., Sun, K., Koniusz, P.: Contrastive Laplacian Eigenmaps (2022). https: //arxiv.org/abs/2201.05493

    work page arXiv 2022

  19. [19]

    https://arxiv.org/abs/2303.01028

    Bo, D., Shi, C., Wang, L., Liao, R.: Specformer: Spectral Graph Neural Networks Meet Transformers (2023). https://arxiv.org/abs/2303.01028

    work page arXiv 2023

  20. [20]

    https://arxiv.org/abs/2210

    Liu, N., Wang, X., Bo, D., Shi, C., Pei, J.: Revisiting Graph Contrastive Learn- ing from the Perspective of Graph Spectrum (2022). https://arxiv.org/abs/2210. 02330

    work page 2022

  21. [21]

    In: Advances in Neural Information Processing Systems (NeurIPS) (2021)

    Zhang, T.,et al.: From canonical correlation analysis to self-supervised graph neu- ral networks. In: Advances in Neural Information Processing Systems (NeurIPS) (2021)

    work page 2021

  22. [22]

    https://arxiv.org/abs/2006.05582

    Hassani, K., Ahmadi, A.H.: Contrastive Multi-View Representation Learning on Graphs (2020). https://arxiv.org/abs/2006.05582

    work page arXiv 2020

  23. [23]

    https://arxiv.org/abs/1601

    Cucuringu, M., Koutis, I., Chawla, S., Miller, G., Peng, R.: Scalable Constrained Clustering: A Generalized Spectral Method (2016). https://arxiv.org/abs/1601. 04746

    work page 2016

  24. [24]

    Signed Graph Convolutional Network

    Derr, T., Ma, Y., Tang, J.: Signed Graph Convolutional Network (2018). https: //arxiv.org/abs/1808.06354

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  25. [25]

    Contrastive Box Embedding for Collaborative Reasoning , isbn =

    Zhang, Z., Liu, J., Zhao, K., Yang, S., Zheng, X., Wang, Y.: Contrastive learning for signed bipartite graphs. In: Proceedings of the 46th Interna- tional ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR ’23, pp. 1629–1638. Association for Computing Machin- ery, New York, NY, USA (2023). https://doi.org/10.1145/3539618.3591...

    work page doi:10.1145/3539618.3591655 2023

  26. [26]

    2024 International Joint Conference on Neural Networks (IJCNN), pp

    Qi, Y., Du, E., Shu, L., Chen, C.: Sgca: Signed graph contrastive learning with adaptive augmentation. In: Proceedings of the 2024 International Joint Confer- ence on Neural Networks (IJCNN), pp. 1–10. IEEE, Yokohama, Japan (2024). https://doi.org/10.1109/IJCNN60899.2024.10651025 26

    work page doi:10.1109/ijcnn60899.2024.10651025 2024

  27. [27]

    Proceedings of the AAAI Conference on Artificial Intelligence37, 4452–4460 (2023)

    Li, Y.,et al.: Signed laplacian graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence37, 4452–4460 (2023)

    work page 2023

  28. [28]

    Information Retrieval3(2), 127–163 (2000) https://doi.org/10.1023/A:1009953814988

    McCallum, A., Nigam, K., Rennie, J., Seymore, K.: Automating the construction of internet portals with machine learning. Information Retrieval3(2), 127–163 (2000) https://doi.org/10.1023/A:1009953814988

    work page doi:10.1023/a:1009953814988 2000

  29. [29]

    In: Proceedings of the Third ACM Conference on Digital Libraries

    Giles, C.L., Bollacker, K.D., Lawrence, S.: Citeseer: an automatic cita- tion indexing system. In: Proceedings of the Third ACM Conference on Digital Libraries. DL ’98, pp. 89–98. Association for Computing Machin- ery, New York, NY, USA (1998). https://doi.org/10.1145/276675.276685 . https://doi.org/10.1145/276675.276685

    work page doi:10.1145/276675.276685 1998

  30. [30]

    In: Proceedings of the Workshop on Mining and Learning with Graphs (MLG)

    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:mlg12- wkshp/namata-mlg12.pdf

    work page 2012

  31. [31]

    Wiki-cs: A wikipedia-based benchmark for graph neural networks.arXiv preprint arXiv:2007.02901, 2020

    Mernyei, P., Cangea, C.: Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks (2022). https://arxiv.org/abs/2007.02901

    work page arXiv 2022

  32. [32]

    Image-based Recommendations on Styles and Substitutes

    McAuley, J., Targett, C., Shi, Q., Hengel, A.: Image-based Recommendations on Styles and Substitutes (2015). https://arxiv.org/abs/1506.04757

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  33. [33]

    arXiv preprint arXiv:2005.00687 , year=

    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

    work page arXiv 2021

  34. [34]

    Semi-Supervised Classification with Graph Convolutional Networks

    Kipf, T.N., Welling, M.: Semi-Supervised Classification with Graph Convolutional Networks (2017). https://arxiv.org/abs/1609.02907

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  35. [35]

    Graph Attention Networks

    Veliˇ ckovi´ c, P., Cucurull, G., Casanova, A., Romero, A., Li` o, P., Bengio, Y.: Graph Attention Networks (2018). https://arxiv.org/abs/1710.10903

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  36. [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 sole...

    work page internal anchor Pith review Pith/arXiv arXiv 2018