Abstract
Social networks have recently garnered considerable interest. With the intention of utilizing social networks for the Semantic Web, several studies have examined automatic extraction of social networks. However, most methods have addressed extraction of the strength of relations. Our goal is extracting the underlying relations between entities that are embedded in social networks. To this end, we propose a method that automatically extracts labels that describe relations among entities. Fundamentally, the method clusters similar entity pairs according to their collective contexts in Web documents. The descriptive labels for relations are obtained from results of clustering. The proposed method is entirely unsupervised and is easily incorporated with existing social network extraction methods. Our experiments conducted on entities in researcher social networks and political social networks achieved clustering with high precision and recall. The results showed that our method is able to extract appropriate relation labels to represent relations among entities in the social networks.
Introduction
While automated tools can already extract social networks from the Web by analyzing name co-occurrences, they typically only provide a numerical weight representing the "strength" of a connection. They fail to explain the qualitative nature of the relationship—whether a link between two individuals represents a boss-employee dynamic, a co-authorship, or a political rivalry.
Existing attempts to label these relations often rely on supervised machine learning, which requires massive, manually annotated datasets that are expensive and time-consuming to create. Furthermore, supervised models are often limited to a few pre-defined categories. This research introduces a domain-independent, unsupervised approach that discovers relationship labels directly from the collective context of the Web, allowing for the identification of niche or emerging relationship types without prior human labeling.
The Proposed Pipeline
The core hypothesis of this method is that entity pairs sharing a similar relationship will appear in similar textual contexts across the Web. The system follows a multi-step pipeline to transform raw web data into labeled social links.
- Context Collection: For every pair of entities (e.g., "Junichiro Koizumi" and "Japan"), the system queries a search engine and downloads the top 100 web pages where they co-occur.
- Context Modeling: It extracts a "local context"—a window of text surrounding the two names. This is represented as a bag-of-words vector, weighted using TF-IDF (Term Frequency-Inverse Document Frequency) to highlight the most descriptive terms while filtering out common noise.
- Similarity Calculation: The system calculates the cosine similarity between the context vectors of different entity pairs.
- Clustering: It uses Hierarchical Agglomerative Clustering (Complete Linkage) to group entity pairs. Because the method is unsupervised, it continues clustering until a quality threshold is reached, naturally discovering the number of relationship types.
- Label Selection: For each cluster, the system identifies the most representative terms (keyphrases) to serve as the relationship labels.
Experimental Evaluation
The researchers evaluated their method on two distinct social networks: a Political Social Network (143 entity pairs) and a Researcher Social Network (421 entity pairs). The "ground truth" for evaluation was established by having human subjects manually assign labels to these pairs based on their web contexts.
Key Results
The system demonstrated remarkably high performance, particularly when the context window was optimized. The authors found that the size of the text window matters significantly: if the window is too small, vital verbs and nouns are missed; if it is too large, unrelated "noise" from the webpage is introduced.
As shown in the table above, the Political Network achieved a peak F-measure of 0.994 (Precision: 0.992, Recall: 0.995) using an optimized context window ($n=10$ words on the sides and $m=30$ words between entities). In the Researcher Network, the system successfully identified specific clusters for "co-authorship of conference paper," "co-authorship of book," and "same affiliation."
Conclusion and Future Work
By aggregating the "collective context" from multiple web pages, the proposed method effectively filters out the ambiguity of single-page mentions. The automatically extracted labels (e.g., "prime minister," "election," "co-author") closely matched human-assigned labels, proving that the highest-scored terms in a cluster are representative of the underlying relationship.
While the method is largely domain-independent, future work will address scaling the clustering process for millions of entities and refining the window size selection for different languages. The authors suggest integrating these labels into "expert finding" systems or using them to automatically bootstrap ontologies for the Semantic Web.
Summary updated