PaperlayerView exact revision on arXiv

Source-linked AI summary

HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks

Chuan Shi, Xiangnan Kong, Yue Huang, Philip S. Yu, Bin Wu

arXiv:1309.7393v1cs.IRcs.AI

TL;DR

The paper addresses the challenge of measuring relatedness among same- and different-typed objects in heterogeneous networks. It proposes HeteSim, a path-constrained relevance measure with uniform treatment and symmetric, semi-metric properties, together with fast computation strategies. Experiments validate its effectiveness and efficiency for evaluating heterogeneous-object relatedness.

  • Problem

    Similarity search mainly measures same-type objects, leaving the increasingly important problem of relatedness measurement for heterogeneous objects insufficiently addressed.

  • Method

    HeteSim is a path-constrained relevance measure that evaluates same- and different-typed object pairs uniformly along arbitrary search paths while providing symmetric, semi-metric behavior.

  • Results

    Extensive experiments validate HeteSim’s effectiveness and efficiency in evaluating the relatedness of heterogeneous objects.

  • Takeaways & Limitations

    HeteSim provides a general relevance framework applicable to heterogeneous-object evaluation and data-mining tasks requiring properties such as symmetry.

Abstract

from arXiv · show

Similarity search is an important function in many applications, which usually focuses on measuring the similarity between objects with the same type. However, in many scenarios, we need to measure the relatedness between objects with different types. With the surge of study on heterogeneous networks, the relevance measure on objects with different types becomes increasingly important. In this paper, we study the relevance search problem in heterogeneous networks, where the task is to measure the relatedness of heterogeneous objects (including objects with the same type or different types). A novel measure HeteSim is proposed, which has the following attributes: (1) a uniform measure: it can measure the relatedness of objects with the same or different types in a uniform framework; (2) a path-constrained measure: the relatedness of object pairs are defined based on the search path that connect two objects through following a sequence of node types; (3) a semi-metric measure: HeteSim has some good properties (e.g., self-maximum and symmetric), that are crucial to many data mining tasks. Moreover, we analyze the computation characteristics of HeteSim and propose the corresponding quick computation strategies. Empirical studies show that HeteSim can effectively and efficiently evaluate the relatedness of heterogeneous objects.

I. INTRODUCTION

The paper frames relevance search in heterogeneous networks as measuring relatedness among same- or different-typed objects, where existing similarity measures are insufficient. It proposes HeteSim as a path-constrained, uniform, symmetric, semi-metric framework with fast computation strategies and empirical validation.

  • Motivation: Relevance search measures relatedness among heterogeneous objects, including pairs with the same or different types, rather than only same-type similarity.The problem arises because different-typed objects can be meaningfully related in applications such as recommendation and profile extraction.
  • Challenges: Heterogeneous networks make relevance measurement difficult because object types, link semantics, and connecting paths differ.Different search paths encode different semantics and can yield different relatedness values.
  • Challenges: A desirable measure should be path-dependent, since search paths capture semantic information and determine meaningful relatedness values.The introduction contrasts paths connecting authors and conferences through direct publication relations with paths incorporating shared subjects.
  • HeteSim: HeteSim provides a uniform measure for same- and different-typed objects while supporting arbitrary search paths and symmetric scores.The framework is designed to handle symmetric or asymmetric paths with one score for each object pair.
  • HeteSim: HeteSim is a semi-metric measure with properties such as symmetry and self-maximum, supporting applications including clustering and collaborative filtering.The paper also analyzes computation and proposes fast strategies; experiments validate effectiveness and efficiency.

II. RELATED WORK

Prior similarity measures largely target same-type objects or fail to represent heterogeneous path semantics. HeteSim addresses these limitations by supporting arbitrary paths and retaining symmetric, self-maximum behavior.

  • Existing measures: Feature-based and link-based similarity approaches generally do not support relevance measurement across heterogeneous object types.Several established methods focus on same-type objects, while feature-based methods ignore link relations.
  • Existing measures: ECTD lacks path constraints and therefore cannot capture subtle heterogeneous-network path semantics.Its Markov-chain random-walk formulation has useful properties but does not encode a specified path.
  • Existing measures: PathSim handles same-type objects through symmetric paths but is unsuitable for asymmetric paths and different-typed object pairs.Its scope is narrower than the relevance settings considered in this paper.
  • HeteSim: PCRW can measure relatedness between different-typed objects, but its asymmetric property restricts applications.The paper positions HeteSim as allowing arbitrary search paths while retaining symmetric and self-maximum properties.

III. PRELIMINARY

The paper defines heterogeneous information networks through typed objects and relations, then formalizes schema-level relevance paths and their concrete path instances. Different paths encode different semantics and can produce different relatedness values.

  • Network model: A heterogeneous information network contains multiple object or relation types, represented as a typed directed graph with mapping functions for objects and links.A bibliographic network is given as an example containing papers, authors, affiliations, terms, subjects, venues, and conferences.
  • Network model: A network schema specifies object types and the relations existing among those types.The schema serves as a template for the network and distinguishes source and target types of relations.
  • Relevance paths: Different paths between the same object types have different semantics and can yield different relatedness results.For example, APVC emphasizes conferences where authors participated, whereas APSPVC emphasizes conferences publishing papers sharing subjects with the authors’ papers.
  • Relevance paths: A relevance path is a schema-level sequence of relations whose composite relation connects an initial object type to a final object type.Its length equals the number of relations in the path, and a concrete path instance follows the corresponding types and links.
  • Relevance paths: A relevance path is symmetric when its composite relation equals its reverse, as in APA and APCPA.The paper also defines reverse paths and concatenation for composing compatible path sequences.

A. Basic Idea

The basic idea extends similarity by treating objects as related when they are referenced by related objects, while constraining the relation to a specified heterogeneous-network path. The desired measure should work uniformly and symmetrically for arbitrary paths.

  • Basic intuition: Objects are considered related when they are referenced by related objects, an intuition applied to both homogeneous and heterogeneous settings.Examples include similar researchers publishing similar papers and researchers being relevant to conferences where they published.
  • Challenges: In heterogeneous networks, relatedness is path-constrained because a relevance path captures semantic information and constrains the walk.Different paths can represent different meanings for the same pair of object types.
  • Design target: A desired measure should handle symmetric and asymmetric paths uniformly and assign one score to same- or different-typed object pairs.This design target motivates the HeteSim framework introduced in the following section.

B. Path-based Relevance Measure

HeteSim measures relatedness between heterogeneous objects by following a specified relevance path, using opposing random walks that meet at a middle type. The framework also covers self-relation and handles cases with no path-following neighbors.

  • HeteSim defines relatedness for object pairs according to a specified sequence of relations connecting their node types.
  • If either endpoint has no relevant out-neighbors or in-neighbors, HeteSim assigns the pair a relevance value of 0.
  • HeteSim computes relatedness by letting the source follow the path and the target traverse against it until their walks meet.The score averages the relatedness of corresponding out-neighbor and in-neighbor pairs along the path.

C. Decomposition of Relevance Path

HeteSim decomposes relevance paths around a middle type so source- and target-side walks can meet, and decomposes atomic relations with an edge object when needed. The resulting probability-based calculation is normalized to make scores interpretable and bounded.

  • Path decomposition: Odd-length relevance paths are transformed into even-length paths so source and target objects can meet at the same middle type.The transformation inserts a middle type object while preserving the original relation through two composed relations.
  • Path decomposition: An arbitrary relevance path P is split into two equal-length paths, PL and PR, around a middle object M.
  • Atomic-relation decomposition: An atomic relation R is decomposed as RO ◦ RI by inserting an edge object E between the source and target types.Each original relation instance receives an edge-object instance connecting its source and target objects.
  • Atomic-relation decomposition: Before normalization, the example reports HeteSim scores of (0, 0.17, 0.33, 0.17).The example motivates normalization because an object’s self-relatedness can otherwise be below 1.
  • Probability formulation: The reachable probability matrix gives the probability that an object reaches another object under a specified path.It is formed by multiplying the transition matrices for the relations along that path.
  • Normalization: HeteSim is the inner product of source- and target-side probability distributions reaching the middle type, then normalized as their cosine.The normalized score ranges from 0 to 1 and is described as more reasonable in the example.

E. Properties of HeteSim

HeteSim has symmetry and self-maximum properties and satisfies the defining conditions of a semi-metric measure. Its path constraint connects it to SimRank while enabling finer-grained relevance evaluation along selected paths.

  • Self-maximum: HeteSim scores lie in [0, 1] and equal 1 exactly when the two middle-type probability distributions are identical.
  • Semi-metric properties: For same objects, the induced distance dis(s, t) = 1 − HeteSim(s, t) gives dis(s, s) = 0 and satisfies identity of indiscernibles.
  • Semi-metric properties: Different-typed objects can receive HeteSim score 1 when they have the same probability distribution over the middle type.The paper relates this to having similar structure under the given path.
  • Semi-metric properties: Because HeteSim is non-negative, symmetric, and satisfies identity of indiscernibles, the paper classifies it as a semi-metric measure.It does not satisfy the triangle inequality because it is path-based.
  • Connection to SimRank: HeteSim is a path-constrained version of SimRank: summing HeteSim over all possible meta paths yields SimRank when its assumptions apply.HeteSim evaluates meeting probability along a given relevance path, whereas SimRank sums over all possible steps or meta paths.
  • Connection to SimRank: The path constraint lets HeteSim evaluate heterogeneous-object relatedness at finer granularity and requires only the specified path rather than all meta paths.

F. Discussion

The discussion presents HeteSim as a path-based framework designed to measure same- and different-type relatedness while preserving symmetry, and analyzes its computation and path-selection strategies.

  • Computation: Computing HeteSim requires O(ldn2) time for an l-length relevance path, with node pairs evaluating relatedness along that path.Here, n denotes the size of one object type and d summarizes average path connectivity.
  • Computation: HeteSim has lower computational complexity than SimRank, whose stated complexity is O(kdn2T4).SimRank simultaneously iterates over all object-pair types, requiring O(T2n2) space in the discussion.
  • Path selection: Relevance paths may be selected by users, supervised learning, or user-guided information combined with path-selection methods.The paper also notes learnable path weighting through labeled training data as a related strategy.
  • Framework: The method adopts a pairwise random walk model because it supports symmetry and arbitrary path constraints.The discussion contrasts it with random-walk approaches that may require redundant inverse-path combinations.
  • Limitations: The pairwise random walk model faces a limitation when an odd-length relevance path prevents source and target objects from meeting.The paper mentions optional strategies such as assigning the meeting point to address this issue.
  • Framework: HeteSim provides a uniform framework for evaluating the relevance of same- or different-typed objects along arbitrary paths.Its relevance evaluation uses an atomic relation for different-typed objects.

V. EXPERIMENTS

The experiments evaluate HeteSim across three heterogeneous information networks, four case studies, and two learning tasks.

  • Experimental design: HeteSim is evaluated on three datasets using four case studies and two learning tasks.The experiments are intended to validate its effectiveness across heterogeneous-network settings.

A. Datasets

The experiments use DBLP, Movie, and ACM heterogeneous networks to examine profiling, expert finding, relevance search, and semantic recommendation.

  • Datasets: The DBLP network contains papers, conferences, authors, and terms spanning four research areas.It includes 14K papers, 20 conferences, 14K authors, 8.9K terms, and 17K links.
  • Datasets: The Movie network contains movies, actors, directors, and types from Internet Movie Database data.The dataset contains 1.5K movies, 5K actors, 551 directors, and 112 types.
  • Case studies: Automatic object profiling measures an object’s relatedness to objects of various types, such as conferences, affiliations, and authors.For Christos Faloutsos, paths identify conferences, research interests, ACM subjects, and important co-authors.
  • Case studies: HeteSim identifies influential or active researchers by comparing author-conference relatedness scores.The discussion reports that it reveals author-conference pair importance more accurately than PCRW.
  • Case studies: HeteSim captures relevance-path semantics in author similarity and recommends different movies according to different paths.The recommendation examples include shared actors, shared types, and semantic connections involving movie themes.
  • Learning tasks: HeteSim consistently outperforms PCRW on the proximity query task across all nine conferences.The comparison uses AUC scores reported in Table VI.

D. Performance on Clustering Task

The clustering experiments compare HeteSim with path-based and homogeneous similarity measures on conferences, authors, and papers. HeteSim achieves the best weighted-average clustering accuracy and has among the shortest running times.

  • The experiments evaluate conference, author, and paper clustering on DBLP using CPAPC, APCPA, and PAPCPAP paths.
  • HeteSim achieves the best performances on author and paper clustering and third place on conference clustering.
  • HeteSim performs best on the weighted average of clustering accuracy across conferences, authors, and papers.
  • HeteSim and PCWR have the smallest representative running times because they require only one matrix multiplication along the path.
  • HeteSim performs well for same-typed similarity and shows potential for clustering with high efficiency.
  • Computation characteristics: The relevance computation phase dominates HeteSim’s running time, while the MUL-phase share increases with path length.

C. Quick Computation Experiments

The quick-computation experiments evaluate four strategies across paths and path lengths using running time and recall. Truncation, hybrid, and Monte Carlo strategies can provide large speedups, while accuracy depends on the strategy and matrix conditions.

  • The experiments compare four quick-computation strategies and the original method across four paths with repetition counts from 1 to 5.
  • The truncation and hybrid strategies significantly accelerate HeteSim and have similar speedup ratios under most conditions.
  • The Monte Carlo strategy has the highest speedup ratio on most conditions except the APA path, but its accuracy fluctuates across paths.
  • The dynamic-programming strategy preserves accuracy close to 1 but usually provides little speedup because it accelerates only the MUL phase.
  • The truncation strategy has high speedup but lower accuracy because it keeps matrices sparse through information loss.
  • The strategies are condition-dependent: very sparse or low-dimensional matrices need no acceleration, while Monte Carlo requires choosing K to balance efficiency and effectiveness.
  • For dense or high-dimensional matrices, hybrid and Monte Carlo speedups reach up to 100 with little accuracy loss.
Loading 1309.7393v1…