pith. sign in

arxiv: 1907.00544 · v1 · pith:NE3ZJGAQnew · submitted 2019-07-01 · 💻 cs.SI · cs.LG

Unsupervised Adversarial Graph Alignment with Graph Embedding

Chaoqi Chen , Weiping Xie , Tingyang Xu , Yu Rong , Wenbing Huang , Xinghao Ding , Yue Huang , Junzhou Huang This is my paper

Pith reviewed 2026-05-25 12:12 UTC · model grok-4.3

classification 💻 cs.SI cs.LG
keywords graph alignmentunsupervised learningadversarial traininggraph embeddingnetwork alignmentsocial networkslink prediction
0
0 comments X

The pith

Unsupervised adversarial training can align two graph embedding spaces without anchor links or attributes.

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

This paper tries to establish that graph alignment is possible without any labeled correspondences by learning embeddings for each graph on its own and then aligning those spaces through adversarial training. A reader would care because many real social networks cannot share user identities due to privacy rules. The method adds a refinement step and an incremental version that discovers new links to bootstrap better embeddings. If the approach holds, alignment becomes feasible in fully unlabeled settings and supports tasks such as cross-network link prediction.

Core claim

The authors claim that their UAGA framework learns separate embeddings for each graph and aligns the spaces via adversarial training in the absence of anchor links or attributes, with a subsequent refinement, and that extending it to iUAGA by iteratively incorporating pseudo anchor links further improves embedding quality and alignment accuracy.

What carries the argument

The adversarial training process that trains a mapping function to make embeddings from one graph indistinguishable from those of the other graph by a discriminator.

If this is right

  • The aligned embeddings improve link prediction performance in social networks.
  • The incremental iUAGA version reveals unobserved user links to boost both embedding and alignment.
  • Experiments on real-world data confirm the effectiveness of UAGA and iUAGA for unsupervised alignment.

Where Pith is reading between the lines

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

  • This adversarial alignment technique could extend to matching graphs in other domains such as citation networks or biological interaction graphs.
  • Combining the unsupervised method with limited attribute data might yield hybrid approaches that require fewer labels.

Load-bearing premise

The embeddings learned independently from each graph contain sufficient overlapping structural information for the adversarial process to discover a meaningful mapping.

What would settle it

If experiments on pairs of graphs with no true correspondences show alignment accuracy no higher than random selection of node pairs, the claim that adversarial training produces useful alignments would be falsified.

Figures

Figures reproduced from arXiv: 1907.00544 by Chaoqi Chen, Junzhou Huang, Tingyang Xu, Weiping Xie, Wenbing Huang, Xinghao Ding, Yue Huang, Yu Rong.

Figure 1
Figure 1. Figure 1: The architectures of the proposed UAGA and iUAGA models. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The illustration of graph extension by constructing pseudo user links [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: By leveraging the pseudo-labeled user links, we [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The Precision@1 result for (a) Last.fm-Last.fm graphs, (b) Flickr [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The t-SNE visualization of the source and target graph embedding [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
read the original abstract

Graph alignment, also known as network alignment, is a fundamental task in social network analysis. Many recent works have relied on partially labeled cross-graph node correspondences, i.e., anchor links. However, due to the privacy and security issue, the manual labeling of anchor links for diverse scenarios may be prohibitive. Aligning two graphs without any anchor links is a crucial and challenging task. In this paper, we propose an Unsupervised Adversarial Graph Alignment (UAGA) framework to learn a cross-graph alignment between two embedding spaces of different graphs in a fully unsupervised fashion (\emph{i.e.,} no existing anchor links and no users' personal profile or attribute information is available). The proposed framework learns the embedding spaces of each graph, and then attempts to align the two spaces via adversarial training, followed by a refinement procedure. We further extend our UAGA method to incremental UAGA (iUAGA) that iteratively reveals the unobserved user links based on the pseudo anchor links. This can be used to further improve both the embedding quality and the alignment accuracy. Moreover, the proposed methods will benefit some real-world applications, \emph{e.g.,} link prediction in social networks. Comprehensive experiments on real-world data demonstrate the effectiveness of our proposed approaches UAGA and iUAGA for unsupervised graph alignment.

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 proposes the UAGA framework for unsupervised graph alignment: separate graph embeddings are learned for each input graph, the embedding spaces are aligned via adversarial training (no anchor links or node attributes), a refinement step generates pseudo-anchors, and the method is extended to iUAGA for iterative improvement of both embeddings and alignment. The abstract claims that comprehensive experiments on real-world data demonstrate effectiveness for alignment and downstream tasks such as link prediction.

Significance. If the central claim holds, the work would address a practically important setting (privacy-constrained alignment without anchors or attributes) and the incremental extension is a constructive addition. The manuscript does not, however, supply machine-checked proofs, parameter-free derivations, or falsifiable predictions that would strengthen the assessment.

major comments (2)
  1. [§3] §3 (method description): the adversarial objective matches marginal distributions of the two embedding spaces but supplies no identifiability argument, regularizer, or analysis showing why the resulting mapping recovers the correct node bijection rather than any other distribution-preserving permutation. This is load-bearing for the claim that node correspondences can be recovered without anchors.
  2. [Experiments] Experiments section: the abstract asserts effectiveness on real-world data, yet the provided text contains no quantitative results, baseline comparisons, ablation studies, or error analysis on the refinement step; without these, it is impossible to evaluate whether the bootstrap from pseudo-anchors succeeds or amplifies early errors.
minor comments (2)
  1. Notation for the adversarial loss weights and the refinement threshold is introduced without an explicit table of symbols or default values.
  2. The abstract would be clearer if it named the real-world datasets and reported at least one key metric (e.g., alignment accuracy or AUC).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and constructive comments. We address each major point below and indicate the changes made to the manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (method description): the adversarial objective matches marginal distributions of the two embedding spaces but supplies no identifiability argument, regularizer, or analysis showing why the resulting mapping recovers the correct node bijection rather than any other distribution-preserving permutation. This is load-bearing for the claim that node correspondences can be recovered without anchors.

    Authors: We agree this is a substantive limitation. The adversarial loss aligns marginal distributions of the embedding spaces but provides no formal identifiability result guaranteeing recovery of the true node bijection (as opposed to another distribution-preserving mapping). In the revised manuscript we have added a dedicated limitations paragraph in §3 that explicitly states this gap, notes the reliance on empirical structural similarity between the input graphs, and clarifies that stronger theoretical guarantees would require additional assumptions on the underlying graph distributions. No new regularizer or proof is introduced, as developing one lies outside the current scope. revision: partial

  2. Referee: [Experiments] Experiments section: the abstract asserts effectiveness on real-world data, yet the provided text contains no quantitative results, baseline comparisons, ablation studies, or error analysis on the refinement step; without these, it is impossible to evaluate whether the bootstrap from pseudo-anchors succeeds or amplifies early errors.

    Authors: The full manuscript contains Section 4 with quantitative alignment accuracy, link-prediction results, comparisons against both supervised and unsupervised baselines, component ablations, and iterative refinement analysis for iUAGA. If the version sent to the referee omitted these tables or figures, we will ensure the revised submission includes all experimental material with an expanded error analysis subsection on pseudo-anchor quality and potential error amplification. We have also added a short discussion of failure cases observed during refinement. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper describes a UAGA framework that first learns separate graph embeddings, then applies adversarial training for alignment, followed by a refinement step using pseudo-anchors. No equations, fitting procedures, or self-citations are quoted that reduce any claimed prediction or result to an input by construction. The central steps rely on external assumptions about adversarial objectives and embedding methods rather than self-referential definitions or fitted quantities renamed as outputs. The derivation remains independent of its own fitted values.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The approach rests on the standard assumption that graph embeddings preserve enough structural signal for cross-graph matching and on the usual hyperparameters of embedding and adversarial training; no invented entities are introduced.

free parameters (2)
  • embedding dimension
    Standard hyperparameter for node embedding methods; value not stated in abstract.
  • adversarial loss weights and learning rates
    Typical tunable parameters in adversarial training; not specified.
axioms (1)
  • domain assumption Separately learned graph embeddings contain sufficient structural information to permit alignment by distribution matching.
    Invoked by the claim that adversarial training on the embedding spaces produces useful alignment.

pith-pipeline@v0.9.0 · 5775 in / 1132 out tokens · 26573 ms · 2026-05-25T12:12:59.125719+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 5 internal anchors

  1. [1]

    Link prediction and recommendation across heterogeneous social net- works,

    Y . Dong, J. Tang, S. Wu, J. Tian, N. V . Chawla, J. Rao, and H. Cao, “Link prediction and recommendation across heterogeneous social net- works,” in 2012 IEEE 12th International Conference on Data Mining , pp. 181–190, IEEE, 2012

    work page 2012

  2. [2]

    Meta-path based multi-network collective link prediction,

    J. Zhang, P. S. Yu, and Z.-H. Zhou, “Meta-path based multi-network collective link prediction,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 1286–1295, ACM, 2014

    work page 2014

  3. [3]

    Personalized recommendation via cross-domain triadic factorization,

    L. Hu, J. Cao, G. Xu, L. Cao, Z. Gu, and C. Zhu, “Personalized recommendation via cross-domain triadic factorization,” in Proceedings of the 22nd international conference on World Wide Web , pp. 595–606, ACM, 2013

    work page 2013

  4. [4]

    Matching users and items across domains to improve the recommendation quality,

    C.-Y . Li and S.-D. Lin, “Matching users and items across domains to improve the recommendation quality,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 801–810, ACM, 2014

    work page 2014

  5. [5]

    An iterative global structure-assisted labeled network aligner,

    A. Yas ¸ar and ¨U. V . C ¸ ataly¨urek, “An iterative global structure-assisted labeled network aligner,” in Proceedings of the 24nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pp. 2614–2623, ACM, 2018

    work page 2018

  6. [6]

    Adaptive sampling towards fast graph representation learning,

    W. Huang, T. Zhang, Y . Rong, and J. Huang, “Adaptive sampling towards fast graph representation learning,” in Advances in Neural Information Processing Systems, pp. 4558–4567, 2018

    work page 2018

  7. [7]

    Semi- supervised graph classification: A hierarchical graph perspective,

    J. Li, Y . Rong, H. Cheng, H. Meng, W. Huang, and J. Huang, “Semi- supervised graph classification: A hierarchical graph perspective,” 2019

    work page 2019

  8. [8]

    Global alignment of multiple protein interaction networks with application to functional orthology detection,

    R. Singh, J. Xu, and B. Berger, “Global alignment of multiple protein interaction networks with application to functional orthology detection,” Proceedings of the National Academy of Sciences , 2008

    work page 2008

  9. [9]

    Algo- rithms for large, sparse network alignment problems,

    M. Bayati, M. Gerritsen, D. F. Gleich, A. Saberi, and Y . Wang, “Algo- rithms for large, sparse network alignment problems,” in Data Mining,

    work page

  10. [10]

    Ninth IEEE International Conference on , pp

    ICDM’09. Ninth IEEE International Conference on , pp. 705–710, IEEE, 2009

    work page 2009

  11. [11]

    Big-align: Fast bipartite graph alignment,

    D. Koutra, H. Tong, and D. Lubensky, “Big-align: Fast bipartite graph alignment,” in 2013 IEEE 13th International Conference on Data Mining, pp. 389–398, IEEE, 2013

    work page 2013

  12. [12]

    Final: Fast attributed network alignment,

    S. Zhang and H. Tong, “Final: Fast attributed network alignment,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pp. 1345–1354, ACM, 2016

    work page 2016

  13. [13]

    Inferring anchor links across multiple heterogeneous social networks,

    X. Kong, J. Zhang, and P. S. Yu, “Inferring anchor links across multiple heterogeneous social networks,” in Proceedings of the 22nd ACM international conference on Information & Knowledge Management , pp. 179–188, ACM, 2013

    work page 2013

  14. [14]

    Connecting users across social media sites: a behavioral-modeling approach,

    R. Zafarani and H. Liu, “Connecting users across social media sites: a behavioral-modeling approach,” in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 41–49, ACM, 2013

    work page 2013

  15. [15]

    Mapping users across networks by manifold alignment on hypergraph.,

    S. Tan, Z. Guan, D. Cai, X. Qin, J. Bu, and C. Chen, “Mapping users across networks by manifold alignment on hypergraph.,” in AAAI, vol. 14, pp. 159–165, 2014

    work page 2014

  16. [16]

    Aligning users across social networks using network embedding.,

    L. Liu, W. K. Cheung, X. Li, and L. Liao, “Aligning users across social networks using network embedding.,” in IJCAI, pp. 1774–1780, 2016

    work page 2016

  17. [17]

    Predict anchor links across social networks via an embedding approach.,

    T. Man, H. Shen, S. Liu, X. Jin, and X. Cheng, “Predict anchor links across social networks via an embedding approach.,” in IJCAI, vol. 16, pp. 1823–1829, 2016

    work page 2016

  18. [18]

    A generalized solution of the orthogonal procrustes problem,

    P. H. Sch ¨onemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika, vol. 31, no. 1, pp. 1–10, 1966

    work page 1966

  19. [19]

    A new graph-based method for pairwise global network alignment,

    G. W. Klau, “A new graph-based method for pairwise global network alignment,” BMC bioinformatics, vol. 10, no. 1, p. S59, 2009

    work page 2009

  20. [20]

    Hydra: Large- scale social identity linkage via heterogeneous behavior modeling,

    S. Liu, S. Wang, F. Zhu, J. Zhang, and R. Krishnan, “Hydra: Large- scale social identity linkage via heterogeneous behavior modeling,” in Proceedings of the 2014 ACM SIGMOD international conference on Management of data , pp. 51–62, ACM, 2014

    work page 2014

  21. [21]

    Comsoc: adaptive transfer of user behaviors over composite social network,

    E. Zhong, W. Fan, J. Wang, L. Xiao, and Y . Li, “Comsoc: adaptive transfer of user behaviors over composite social network,” in Proceed- ings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 696–704, ACM, 2012

    work page 2012

  22. [22]

    Multiple anonymized social networks align- ment,

    J. Zhang and S. Y . Philip, “Multiple anonymized social networks align- ment,” in Data Mining (ICDM), 2015 IEEE International Conference on, pp. 599–608, IEEE, 2015

    work page 2015

  23. [23]

    Structural deep network embedding,

    D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 1225–1234, ACM, 2016

    work page 2016

  24. [24]

    Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec,

    J. Qiu, Y . Dong, H. Ma, J. Li, K. Wang, and J. Tang, “Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec,” in Proceedings of the Eleventh ACM International Confer- ence on Web Search and Data Mining , pp. 459–467, ACM, 2018

    work page 2018

  25. [25]

    SimplE Embedding for Link Prediction in Knowledge Graphs

    S. M. Kazemi and D. Poole, “Simple embedding for link prediction in knowledge graphs,” arXiv preprint arXiv:1802.04868 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  26. [26]

    Deepwalk: Online learning of social representations,

    B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 701–710, ACM, 2014

    work page 2014

  27. [27]

    Line: Large-scale information network embedding,

    J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in Proceedings of the 24th International Conference on World Wide Web , pp. 1067–1077, International World Wide Web Conferences Steering Committee, 2015

    work page 2015

  28. [28]

    node2vec: Scalable feature learning for networks,

    A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 855–864, ACM, 2016

    work page 2016

  29. [29]

    Distributed representations of words and phrases and their composition- ality,

    T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their composition- ality,” in Advances in neural information processing systems , pp. 3111– 3119, 2013

    work page 2013

  30. [30]

    Efficient Estimation of Word Representations in Vector Space

    T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” arXiv preprint arXiv:1301.3781 , 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  31. [31]

    Generative adversarial nets,

    I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y . Bengio, “Generative adversarial nets,” in Advances in neural information processing systems , pp. 2672–2680, 2014

    work page 2014

  32. [32]

    Improving zero-shot learning by mitigating the hubness problem

    G. Dinu, A. Lazaridou, and M. Baroni, “Improving zero-shot learning by mitigating the hubness problem,” arXiv preprint arXiv:1412.6568 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  33. [33]

    Billion-scale similarity search with GPUs

    J. Johnson, M. Douze, and H. J ´egou, “Billion-scale similarity search with gpus,” arXiv preprint arXiv:1702.08734 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  34. [34]

    Offline bilingual word vectors, orthogonal transformations and the inverted softmax

    S. L. Smith, D. H. Turban, S. Hamblin, and N. Y . Hammerla, “Offline bilingual word vectors, orthogonal transformations and the inverted softmax,” arXiv preprint arXiv:1702.03859 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  35. [35]

    Parseval networks: Improving robustness to adversarial examples,

    M. Cisse, P. Bojanowski, E. Grave, Y . Dauphin, and N. Usunier, “Parseval networks: Improving robustness to adversarial examples,” in Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 854–863, JMLR. org, 2017

    work page 2017

  36. [36]

    The link-prediction problem for social networks,

    D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” Journal of the American society for information science and technology , vol. 58, no. 7, pp. 1019–1031, 2007

    work page 2007

  37. [37]

    Decaf: A deep convolutional activation feature for generic visual recognition,

    J. Donahue, Y . Jia, O. Vinyals, J. Hoffman, N. Zhang, E. Tzeng, and T. Darrell, “Decaf: A deep convolutional activation feature for generic visual recognition,” in International conference on machine learning , pp. 647–655, 2014

    work page 2014