Abstract
Recently, many Web services such as social networking services, blogs, and collaborative tagging have become widely popular. Many attempts are being made to investigate user interactions by analyzing social networks among users. However, analyzing a social network with attributional data is often not an easy task because numerous ways exist to define features through aggregation of different tables. In this study, we propose an algorithm to identify important network-based features systematically from a given social network to analyze user behavior efficiently and to expand the services. We apply our method for link-based classification and link prediction tasks with two different datasets, i.e., an @cosme (an online viral marketing site) dataset and a Hatena Bookmark (collaborative tagging service) dataset, to demonstrate the usefulness of our algorithm. Our algorithm is general and can provide useful network-based features for social network analyses.
Introduction: The Feature Engineering Bottleneck
In the realm of social network analysis (SNA), researchers frequently encounter the challenge of "feature engineering"—the arduous process of transforming raw graph data into structured variables suitable for machine learning models. While standard metrics like degree centrality or betweenness centrality are widely used, they are often selected based on researcher intuition rather than a systematic exploration of the available data.
Social data is inherently relational and multi-layered, offering nearly infinite ways to aggregate information about a user's local neighborhood, distant connections, and the attributes of those nodes. This paper addresses the lack of a formal, general-purpose algorithm to explore this vast feature space systematically, aiming to find the most predictive indicators for user classification and link prediction.
Methodology: A Systematic Feature Pipeline
The core of the proposed approach is a four-step pipeline designed to generate complex features from simple primitives. This framework allows the system to "re-discover" classic social network indices and identify entirely new ones:
- Node Set Selection: Define the scope of nodes relative to a target (e.g., all nodes within distance $k$ of user $x$).
- Operator Application: Apply a function to these nodes to generate a list of values, such as geodesic distance ($t$) or structural equivalence ($e_x$).
- Aggregation: Collapse the list of values into a single numeric feature using functions like Sum, Average, Maximum, or Minimum.
- Secondary Aggregation: Optionally combine two values from the previous step (e.g., calculating a ratio or difference) to create complex relational features.
As shown in Figure 1, a complex metric like Closeness Centrality can be represented as the Average of the Distances to all Reachable Nodes. By nesting these operations, the algorithm can explore a wide variety of feature combinations, categorized into "Methods 1 through 4" based on increasing complexity.
Datasets and Experimental Setup
The study evaluates the algorithm on two prominent Japanese social datasets:
- @cosme: The largest online community for women in Japan, centered on cosmetic reviews. The task was link-based classification: predicting whether a user would join a specific community.
- Hatena Bookmark: A collaborative social bookmarking service. The task was link/tag prediction: determining if a user would apply a specific tag based on social similarity.
These datasets present a significant challenge because the "negative examples" were not chosen at random but from users already in the vicinity of the target community, requiring highly precise features to achieve accurate classification.
Key Results and Performance
The systematic approach consistently outperformed baseline models that relied on manually selected features. The results demonstrate that as the complexity of the feature generation pipeline increases (from Method 1 to Method 4), the model's predictive power improves significantly.
As detailed in Figure 4, the F-value for the @cosme dataset improved from a baseline of 0.495 to 0.604 using Method 4. Similar gains were observed in the Hatena Bookmark dataset, where Method 4 achieved an F-value of 0.717 compared to the baseline's 0.661. Furthermore, in link prediction tasks, the proposed Method 2 (F-value 0.613) vastly outperformed traditional metrics like the Jaccard coefficient (0.232) and Adamic/Adar (0.270).
Insights and Conclusion
The study reveals several key insights into social network dynamics. First, complex social metrics are effectively combinations of simple primitives; treating feature generation as a search problem allows for the discovery of indices that outperform traditional ones. Second, looking beyond immediate neighborhoods (to distance 2 or more) significantly improves accuracy. Finally, the framework successfully re-discovered "structural equivalence" as a major predictor of behavior, validating its sociological relevance.
While the method faces challenges regarding "feature explosion" and computational complexity for certain iterative operators, it provides a robust, generalizable framework for social network analysis. Future work will focus on integrating these automatically generated features into real-time recommendation systems for friends and products.
Summary updated