PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction

Hongxu Chen, Hongzhi Yin, Xiangguo Sun, Tong Chen, Bogdan Gabrys, Katarzyna Musial

arXiv:2006.01963v1cs.SIcs.LG

TL;DR

Cross-platform account matching is constrained by unavailable user-generated information and insufficient network topology, especially in sparse settings. MGCN unifies simple-graph and hypergraph convolutions and adds two-phase space reconciliation for scalable training and cross-network alignment. Experiments on two large-scale real-world networks show that it outperforms state-of-the-art models.

  • Problem

    Existing account-matching methods rely on user content or face data insufficiency when using network topology alone.

  • Method

    MGCN jointly learns embeddings with local simple-graph and hypergraph convolutions, using partitioning and two-phase space reconciliation for large networks.

  • Results

    MGCN consistently and significantly outperforms all baselines across evaluation metrics on Facebook-Twitter and Douban-Weibo.

  • Takeaways & Limitations

    The unified graph-convolution framework supports accurate anchor-link prediction without necessarily relying on demographic information and scales to large social networks.

Abstract

from arXiv · show

Cross-platform account matching plays a significant role in social network analytics, and is beneficial for a wide range of applications. However, existing methods either heavily rely on high-quality user generated content (including user profiles) or suffer from data insufficiency problem if only focusing on network topology, which brings researchers into an insoluble dilemma of model selection. In this paper, to address this problem, we propose a novel framework that considers multi-level graph convolutions on both local network structure and hypergraph structure in a unified manner. The proposed method overcomes data insufficiency problem of existing work and does not necessarily rely on user demographic information. Moreover, to adapt the proposed method to be capable of handling large-scale social networks, we propose a two-phase space reconciliation mechanism to align the embedding spaces in both network partitioning based parallel training and account matching across different social networks. Extensive experiments have been conducted on two large-scale real-life social networks. The experimental results demonstrate that the proposed method outperforms the state-of-the-art models with a big margin.

1 INTRODUCTION

Cross-platform account matching matters for social-network analytics but faces a trade-off between scarce user content and insufficient network structure. MGCN addresses this with multi-level graph convolutions, scalable training, and two-phase embedding reconciliation.

  • Account matching links accounts belonging to the same individual across social networks and supports applications including personalization, link prediction, recommendation, and detection.
  • Existing methods either rely on increasingly unavailable profiles, content, and demographic features or suffer data insufficiency when modeling network structure alone.
  • MGCN jointly uses simple-graph and hypergraph convolutions to learn embeddings at multiple granularities and capture richer network information.
  • For large networks, the framework partitions networks for decentralized training and uses two-phase space reconciliation within networks and across networks.
  • MGCN outperforms state-of-the-art models on two large-scale real-world datasets.

2 PROPOSED METHOD

The proposed method predicts cross-network anchor links by learning network embeddings and reconciling the latent spaces of two social networks. It combines simple-graph and hypergraph processing within a scalable MGCN framework.

  • 2.1 Preliminaries: Anchor link prediction treats pairs of nodes from two networks as binary candidates whose cross-network link existence must be predicted.
  • 2.1.2 Hypergraph: Hypergraphs represent relations involving more than two nodes simultaneously, complementing pairwise simple-graph edges.
  • 2.2 Model Overview: MGCN first convolves over original social-network graphs, refines node embeddings with hypergraph convolution, reconciles the two latent spaces, and classifies candidate pairs.
  • 2.2 Model Overview: Figure 1 presents the multi-level graph convolution framework.

2.3 Convolution on Simple Graphs

The simple-graph convolution stage constructs local adjacency matrices within hyperedges and applies graph convolutions to obtain base node embeddings. It combines direct connectivity with hyperedge-derived weighting before aggregating outputs.

  • Base node embeddings X are obtained by first performing simple-graph convolutions on the original network.
  • For each hyperedge, MGCN applies convolution using a local adjacency matrix Ae, activation σ, node representations Xk_e, and trainable weights Wk.
  • The diagonal matrix Se weights hyperedge connectivity using node-observation possibilities p(v,e), whose calculation depends on the hyperedge definition.
  • The normalized network adjacency uses node degrees, the simple-graph adjacency matrix, and the identity matrix before constructing each local hyperedge adjacency.
  • Ae captures direct node connectivity within a hyperedge while weighting it by hyperedge connectivity, combining two local structural signals.
  • Outputs from individual hyperedges are concatenated and mapped back to d dimensions through a dense layer.

2.4 Convolution on Hypergraphs

The method derives hypergraph relationships from node–hyperedge incidence and uses them to extend standard graph convolution. Combined with simple-graph convolution, this multi-level design captures both pairwise and higher-order relations.

  • The incidence matrix H represents node–hyperedge membership, while Dn and De encode node and hyperedge degrees.H(v,e) indicates the relationship between node v and hyperedge e; the degree matrices sum these memberships.
  • Hypergraph convolution replaces standard GCN structural inputs with information derived from the hypergraph’s incidence and adjacency matrices.The hypergraph adjacency is derived as Ah = HH⊤ − Dn, after defining node and hyperedge degrees.
  • The multi-level network first learns embeddings through simple-graph convolution, then applies K hypergraph-convolution layers to produce final representations XK.The final embeddings combine information from pairwise neighborhoods and hyperedges.
  • This combination captures both 1-hop pairwise relations and high-order non-pairwise relations, which is especially important when observed anchor nodes are limited.

2.5 Learning Network Embeddings

The embedding-learning procedure partitions the network with Louvain-based processing and trains embeddings by distinguishing observed edges from sampled negative edges. Bidirectional negative sampling supports optimization of the final-layer representations.

  • Network embeddings maximize positive-edge probabilities while minimizing probabilities for sampled negative edges.The sigmoid function η computes the probability of observing an edge.
  • Bidirectional negative sampling fixes each endpoint in turn and draws M negative nodes from a degree-smoothed noise distribution Pn(v) ∼ d_v^0.75.Optimizing this objective yields embeddings in the final convolution layer for downstream anchor-link prediction.
  • Algorithm 1 generates graph partitions with Louvain and iteratively processes them under specified size bounds Nmin and Nmax.The algorithm takes G, Nmax, Nmin, and iteration count T as inputs and outputs a partition set.

2.6 Anchor Link Prediction

Anchor-link prediction first reconciles the independently learned embeddings of two networks into a shared latent space. It then classifies concatenated cross-network node representations using a fully connected network.

  • The two networks’ embeddings cannot be matched directly because they are learned in different latent spaces with potentially different semantic contexts.
  • The method fixes one network’s embeddings and projects the other into the same space using a learned projection function γ(x|Γ,b) = xΓ + b.Projection parameters are learned by aligning embeddings of observed anchor nodes.
  • For each cross-network node pair, concatenated embeddings are passed to a fully connected network that predicts whether the pair is an anchor link.Cross entropy is used as the anchor-link prediction loss.

2.7 Handling Large-Scale Networks

To scale MGCN to large networks, the framework partitions graphs for decentralized training and reconciles the resulting embedding spaces. The same two-phase alignment idea also supports cross-network anchor-link prediction.

  • Large-scale GCN training faces GPU memory and computation limits because many methods require the global adjacency matrix.Graph partitioning enables parallel deployment of the proposed model.
  • Louvain-based partitioning creates manageable clusters, recursively splitting oversized partitions and assigning undersized ones to existing partitions.
  • Shared nodes and their associated edges are added to every partition, then one partition is fixed while the others are reconciled into its representation space.This resolves the different latent spaces produced by independent partition training.
  • After partition embeddings are matched into a uniform space, the resulting network embeddings can be used for anchor-link prediction.

2.8 Optimization Strategy

MGCN training proceeds in stages: it first learns graph embeddings, then reconciles partitions, reconciles the two networks, and finally optimizes anchor link prediction.

  • 2.8 Optimization Strategy: MGCN sequentially optimizes graph embeddings, partition reconciliation, anchor reconciliation, and the final anchor link prediction objective.The first reconciliation aligns clusters within a network, while the second aligns the two networks.

3 EXPERIMENTS

Experiments on large-scale cross-platform networks evaluate MGCN against multiple baselines, its robustness under sparse or limited-overlap data, hypergraph construction choices, and scalability. MGCN consistently outperforms baselines, remains robust with limited structural or anchor-link information, and adds little propagation time.

  • 3.4 Performance on Anchor Link Prediction: 9.7%, 9.1%, and 9.0% improvements on Facebook-Twitter, and 0.6%, 2.7%, and 2.6% on Douban-Weibo, over second-best Macro Precision, Macro F1, and Macro Recall results, respectively.MGCN consistently outperformed all baselines across both datasets and all reported evaluation metrics.
  • 3.5 Analysis on Model Robustness: MGCN remains the best-performing method even with a small portion of training anchor links, supporting robustness when observed labels are scarce.The evaluation varies the training anchor-link ratio from 10% to 90% while holding out 10% for testing.
  • 3.5.2 Effect of Edge Percentage: MGCN keeps stable performance as edge sparsity varies, because hypergraphs provide additional structural information when physical-network edges are limited.The sparsity parameter αs is varied from 10% to 90%, with results averaged over five executions.
  • 3.5.2 Effect of Edge Percentage: MGCN remains best at 10% network overlap, and its superiority becomes more pronounced as overlap increases.Network overlap measures the shared entities between the two networks; results are averaged over five executions.
  • 3.6 Impact of Hypergraph Construction Strategies: Neighbor-based, anchor-based, and centrality-based hypergraphs perform similarly overall, but centrality-based construction trails on Macro F1 and Macro Recall.The result suggests that carefully handcrafted features are unnecessary for performance improvements.
  • 3.7 Analysis on Model Efficiency: MGCN offers state-of-the-art anchor link prediction while retaining high-level scalability, with only little additional forward-propagation time versus GCN and HGNN.The efficiency comparison measures forward propagation for 1,000 epochs across increasing Facebook subnetwork scales.

4 RELATED WORK

Prior account-matching methods use profiles, content, matrix factorization, or network embeddings, but face data-quality, scalability, or sparsity limitations. The paper positions decentralized hypergraph representation learning and subgraph reconciliation as its proposed response.

  • Traditional methods: Profile- and content-based methods suffer from insufficient high-quality data and constrained practical generalizability.These approaches use attributes such as names, ages, locations, reviews, and posts.
  • Traditional methods: Matrix-factorization approaches are difficult to scale because they require entire network adjacency matrices and struggle with sparsity in large networks.The cited examples include IsoRank, NetAligh, FINAL, and REGAL.
  • Proposed approach: The proposed method uses decentralized hypergraph representation learning with subgraph reconciliation to handle large-scale social networks.This design addresses embedding alignment after decentralized training.
  • Embedding-based approaches: Network embedding research includes matrix-factorization, random-walk, and graph-convolutional approaches for learning node representations.The passage identifies MDS, Spectral Clustering, Graph Factorization, random-walk methods, and GCNs as mainstream approaches.

5 CONCLUSION

The paper concludes that fusing simple-graph and hypergraph convolutions steadily outperforms state-of-the-art methods for anchor link prediction. Network partitioning with two-phase reconciliation supports large-scale datasets, while future work targets automatic hypergraph discovery, multiple networks, unused inter-partition links, temporal analysis, and recommendations.

  • 5 CONCLUSION: Fusing simple-graph and hypergraph information steadily outperforms state-of-the-art methods for anchor link prediction.The conclusion identifies multi-level graph convolution as the core approach.
  • 5 CONCLUSION: Network partitioning and two-phase reconciliation provide a framework for handling large-scale datasets.The conclusion presents these components as the scalability design.
  • 5 CONCLUSION: Future work includes automatic hypergraph discovery, scaling to multiple social networks, using links between partitions, temporal analysis, and recommendation applications.These directions are explicitly listed as extensions of the framework.
Loading 2006.01963v1…