Source-linked AI summary
Name Disambiguation in Anonymized Graphs using Network Embedding
Baichuan Zhang, Mohammad Al Hasan
TL;DR
Name disambiguation must separate documents for people who share a name, but biographical and external features may be unavailable or raise privacy concerns. This paper uses anonymized relational graphs to embed documents for clustering, and reports significantly better results than existing methods on multiple datasets. Its scope is a setting where node attributes and external-source information are not used.
Problem
Name disambiguation must separate documents associated with the same name, while many existing methods rely on biographical or external features that may be unavailable or raise privacy concerns.
Source: §1 · p. 1Method
Results
The authors report that their method significantly outperforms existing state-of-the-art methods on multiple real-life name-disambiguation datasets.
Source: §1 · p. 2, §6 · p. 10Takeaways & Limitations
The authors conclude that their ranking-based model clusters documents for a single person better than other network-embedding methods and is useful when node attributes are unavailable.
Source: §6 · p. 10The study restricts the task to anonymized graphs with network topology as the available information, excluding bibliographical features and external-source information.
Source: §3 · p. 3
Abstract
from arXiv · showhide
In real-world, our DNA is unique but many people share names. This phenomenon often causes erroneous aggregation of documents of multiple persons who are namesake of one another. Such mistakes deteriorate the performance of document retrieval, web search, and more seriously, cause improper attribution of credit or blame in digital forensic. To resolve this issue, the name disambiguation task is designed which aims to partition the documents associated with a name reference such that each partition contains documents pertaining to a unique real-life person. Existing solutions to this task substantially rely on feature engineering, such as biographical feature extraction, or construction of auxiliary features from Wikipedia. However, for many scenarios, such features may be costly to obtain or unavailable due to the risk of privacy violation. In this work, we propose a novel name disambiguation method. Our proposed method is non-intrusive of privacy because instead of using attributes pertaining to a real-life person, our method leverages only relational data in the form of anonymized graphs. In the methodological aspect, the proposed method uses a novel representation learning model to embed each document in a low dimensional vector space where name disambiguation can be solved by a hierarchical agglomerative clustering algorithm. Our experimental results demonstrate that the proposed method is significantly better than the existing name disambiguation methods working in a similar setting.
1 INTRODUCTION
The paper addresses name disambiguation when personal attributes are unavailable or privacy-sensitive, using anonymized relational graphs to embed documents for person-level clustering. It reports better performance than existing methods in privacy-preserving settings.
1 INTRODUCTION
- Many existing methods rely on biographical or external features that may be costly, unavailable, or inappropriate to obtain in privacy-sensitive settings.Prior anonymized-graph approaches also use only collaboration networks and address binary ambiguity detection rather than partitioning records by person.Source: §1 · pp. 1–2
- The task partitions documents associated with one name reference into groups, each corresponding to a unique real-life person.The paper frames this as clustering the document-document graph.Source: §1 · p. 2
- A joint representation-learning model embeds anonymized person-person, person-document, and document-document graphs, then applies hierarchical clustering to the document vectors.Its pairwise-ranking objective is designed for clustering by optimizing distances between similar and dissimilar documents.Source: §1 · p. 2
- The proposed method significantly outperforms existing name-disambiguation methods on multiple real-life datasets and in privacy-preserving settings.The introduction also reports superiority over state-of-the-art methodologies in a privacy-preserving setup.Source: §1 · p. 2
2 RELATED WORK
Related work spans supervised, unsupervised, and probabilistic approaches, while privacy-preserving methods use anonymized graph structure. Earlier graph methods have limitations in task scope, and network-embedding approaches differ in their use of multiple graphs and ranking objectives.
2 RELATED WORK
- Name-disambiguation research includes supervised classification, unsupervised clustering, and probabilistic relational models.Examples include Naive Bayes and SVM, K-way spectral clustering, and Markov Random Fields.Source: §2 · p. 2
- Anonymized-graph methods avoid biographical attributes, but some only identify ambiguous entities rather than partitioning documents into person-specific groups.The cited unsupervised approaches also exploit time-stamped network topology.Source: §2 · pp. 2–3
- Unlike LINE’s document-document similarity input and PTE’s need for labeled data, this work jointly learns across multiple networks with a ranking-based loss.The related-work discussion contrasts this with the K-L-divergence objectives used by most existing methods.Source: §2 · p. 3
3 PROBLEM FORMULATION
Name disambiguation partitions documents associated with a shared name into groups for unique real-life people. This work frames it as clustering over anonymized relational graphs, with document similarity based on collaborator relationships.
3 PROBLEM FORMULATION
- Name disambiguation partitions a name reference’s documents into disjoint sets, each corresponding to one real-life person.The task is challenging because document counts per person follow a power-law distribution, producing severe class imbalance.Source: §3 · p. 3
- The study restricts inputs to anonymized graph topology, excluding bibliographical features and external sources to alleviate privacy-violation risk.It represents collaboration, person-document associations, and linked documents in person-person, person-document, and document-document networks.Source: §3 · p. 3
- The person-person network weights each collaboration edge by the number of distinct documents the pair coauthored.The person-document network connects collaborators to documents and weights an edge by the number of times a person appears in a document.Source: §3 · p. 3
- Document similarity uses overlap between collaborators or between their one-hop neighborhoods, rather than word co-occurrence.Word co-occurrence is avoided because a set of unique words can sometimes reveal a person’s identity.Source: §3 · p. 4
- The resulting task is clustering the document-document graph, while a joint embedding lets information pass across all three graphs.The embedding places graph vertices in a shared low-dimensional latent space.Source: §3 · p. 4
4 METHOD
The method jointly embeds anonymized person and document networks using pairwise ranking objectives, then clusters document embeddings with hierarchical agglomerative clustering. It optimizes the embeddings with stochastic gradient descent and analyzes the cost of both stages.
4.1 Model Formulation
- For each network, the formulation seeks embeddings that preserve a ranking between neighboring and non-neighboring nodes.Positive and negative training sets are defined for each relation type.Source: §4.1 · pp. 4–5
- The model jointly embeds person-person, person-document, and document-document relations by minimizing a combined objective with l2 regularization.Its ranking-based objective unifies the three relation types through shared person and document vertices.Source: §4.1 · p. 5
4.2 Model Optimization
- Stochastic gradient descent updates embeddings using edge-weighted sampling of positive instances and uniform sampling of negative instances.The method applies corresponding gradient updates to person-person and person-document training instances as well.Source: §4.2 · pp. 5–6
4.3 Pseudo-code and Complexity Analysis
- The pipeline constructs the graphs and training sets, initializes embeddings, optimizes them, then applies HAC to divide documents into L clusters.The algorithm returns both the document embedding matrix and clustering membership set.Source: §4.3 · p. 6, §4.2 · p. 6
- The stated total complexity is (2|PGpp| + 2|PGpd| + 2|PGdd|)O(k) + O(N^2 log N).The first term covers embedding updates, and the second is the stated cost of hierarchical clustering.Source: §4.3 · p. 6
5 EXPERIMENTS AND RESULTS
The experiments evaluate name-level disambiguation on ambiguous bibliographic references from Arnetminer and CiteSeerX. The comparison set includes designed baselines, network-embedding approaches, and graph-kernel methods.
5 EXPERIMENTS AND RESULTS
- The experiments evaluate the proposed method against other approaches using linked data in a privacy-preserving setting.The paper describes the comparisons as testing whether its method is superior to the alternatives.Source: §5 · p. 6
5.1 Datasets
- The evaluation uses 10 highly ambiguous name references from each of Arnetminer and CiteSeerX, treating each name reference as a distinct dataset.The dataset statistics report document counts and distinct-author counts for each reference.Source: §5.1 · p. 6
5.2 Competing Methods
- The competing methods include designed baselines, embedding methods adapted to document clustering, and graphlet-kernel methods for anonymized graphs.The listed embedding approaches include GF, DeepWalk, LINE, Node2Vec, and PTE; graph kernels use size-3 and size-4 graphlets.Source: §5.2 · pp. 6–7
5.3 Experimental Setting and Implementation
The evaluation compares methods on 20 name references using Macro-F1, and also examines parameter robustness, network contributions, and model convergence. The implementation fixes the embedding dimension and learning rate, tunes regularization, and supplies the ground-truth cluster count to HAC.
5.3 Experimental Setting and Implementation
- Macro-F1, the unweighted average of class-wise F1 scores, evaluates disambiguation across 20 name references.Higher Macro-F1 indicates better disambiguation performance.Source: §5.3 · p. 7
- The experiments test robustness to embedding dimension and cluster count, incrementally add the three network types, and examine learning-model convergence.The networks are person-person, person-document, and document-document.Source: §5.3 · p. 7
- The embedding dimension is 20, the learning rate is 0.02, and regularization is grid-searched over {0.001, 0.005, 0.01, 0.1, 1, 10}.For evaluation, HAC receives the actual number of classes for each name reference.Source: §5.3 · p. 7
5.4 Comparison among Various Name Disambiguation Methods
Across ArnetMiner and CiteSeerX, the proposed method performs best for most name references and shows a substantial gain on the difficult “S Lee” case. The authors relate its advantage to learning document embeddings that use information across multiple networks.
5.4 Comparison among Various Name Disambiguation Methods
- The proposed method performs best for 9 of 10 ArnetMiner references and 8 of 10 CiteSeerX references.Tables 3 and 4 report Macro-F1 comparisons at embedding dimension 20.Source: §5.4 · p. 8, Table 3 · p. 8, Table 4 · p. 8
- Author-list and graph-kernel methods perform poorly, while embedding-based methods generally learn more effective document features.The authors suggest size-3 and size-4 graphlets may not distinguish documents by author.Source: §5.4 · p. 8
- No competing embedding method clearly wins across references; the authors attribute their method’s advantage to combining information across networks and using a similarity-ranking objective.They note that DeepWalk ignores edge weights, whereas GF and LINE outperform it on most references.Source: §5.4 · p. 9
5.5 Parameter Sensitivity of Embedding Dimension
Embedding dimension affects name-disambiguation performance: Macro-F1 rises and then falls as dimension increases. The authors suggest insufficient representation capacity at small dimensions and overfitting at large dimensions.
5.5 Parameter Sensitivity of Embedding Dimension
- Macro-F1 first increases and then decreases as embedding dimension grows across both datasets.The experiment averages results over 10 name references per dataset and tests dimensions 10, 20, 30, 40, and 50.Source: §5.5 · p. 9
- The authors suggest small dimensions may provide insufficient representation capacity.This is offered as a possible explanation for the lower performance at small dimensions.Source: §5.5 · p. 9
- The authors suggest large dimensions may overfit the data and reduce disambiguation performance.This is offered as a possible explanation for the decline at larger dimensions.Source: §5.5 · p. 9
5.6 Performance Comparison over the Number of Clusters
The method’s Macro-F1 remains higher than GF and LINE across tested cluster counts for “Lei Wang.” This comparison matters because the number of real-life people under a name is generally unknown beforehand.
5.6 Performance Comparison over the Number of Clusters
- The number of real-life persons under a name is generally unknown a priori, motivating comparisons across multiple L values.The experiment supplies varying L values to HAC after document representations are learned.Source: §5.6 · p. 9
- For “Lei Wang” in Arnetminer, our method always outperformed GF and LINE across L = 40, 45, 50, 55, and 60; its overall improvement over both was statistically significant (p < 0.01).The actual number of distinct authors under “Lei Wang” is 48.Source: §5.6 · p. 9
5.7 Component Contribution Analysis
The component analysis adds the person-document, linked-document, and person-person graphs in order. Macro-F1 improves with each addition on both datasets.
5.7 Component Contribution Analysis
- Adding each graph component improves Macro-F1 on both Arnetminer and CiteSeerX.Results are averaged over all 10 name references in each dataset.Source: §5.7 · p. 10
- The components are added in this order: person-document graph, linked-document graph, then person-person graph.The order follows the components’ individual disambiguation performance.Source: §5.7 · p. 10
5.8 Convergence Analysis
The embedding approach converges in approximately 50 epochs for the “Lei Wang” reference, with similar patterns for other name references. Its objective is non-convex, making a global optimum with SGD challenging.
5.8 Convergence Analysis
- Approximately 50 epochs are needed for convergence on “Lei Wang,” with similar convergence patterns for other name references.The analysis reports promising convergence on both pairwise-ranking objective loss and AUC.Source: §5.8 · p. 10
- Because the objective is non-convex, reaching a global optimum with SGD is challenging.The paper suggests decreasing the learning rate as epochs increase or trying multiple runs with different seed initializations.Source: §5.8 · p. 10
6 CONCLUSION
The conclusion presents a relational-data-only representation-learning approach for name disambiguation, with pairwise ranking and strong results across multiple datasets. Its anonymized-graph setting is suited to cases where node attributes are unavailable for privacy reasons.
6 CONCLUSION
- The representation-learning model uses a pairwise-ranking objective to cluster documents belonging to one person better than other network-embedding methods.Source: §6 · p. 10
- Using only relational data makes the method useful for anonymized networks where privacy concerns leave node attributes unavailable.Source: §6 · p. 10
- The method significantly outperforms many existing state-of-the-art name-disambiguation methods on multiple datasets.The conclusion also says its pairwise-ranking objective clusters documents belonging to one person better than other network-embedding methods.Source: §6 · p. 10