Three hypergraph eigenvector centralities

• Graph centrality assumes pairwise relationships, although many systems contain simultaneous interactions among several entities that hypergraphs model more faithfully.Source: §1 · p. 1
• The paper uses eigenvector centrality to mean the principal adjacency-matrix eigenvector, rather than any network centrality scores that form an eigenvector.Source: §1 · pp. 1–2
• For a strongly connected graph, eigenvector centrality requires positive node scores proportional to the scores of each node’s neighbors, yielding Ac = λc.Source: §1 · p. 2
• Perron-Frobenius guarantees a unique positive eigenvector up to scaling for an irreducible adjacency matrix, giving strongly connected graphs well-defined eigenvector centrality.Source: §1 · p. 2

2. Hypergraph eigenvector centralities.

• The framework extends graph eigenvector centrality to m-uniform hypergraphs represented by symmetric adjacency tensors and develops three centralities for strongly connected cases.For symmetric tensors, the connectivity notion matches classical hypergraph connectivity and the connectivity of the hypergraph’s clique expansion.Source: §2 · pp. 2–3

2.1. Clique motif Eigenvector Centrality (CEC)

• CEC uses the principal eigenvector of W, where W_uv counts hyperedges containing u and v, normalized to unit 1-norm.For m ≥ 3, it can also be viewed as a best rank-one approximation of W and as the steady state of a weighted average of infinite paths through the hypergraph.Source: §2.1 · p. 4

2.2. Z-eigenvector centrality (ZEC)

• ZEC uses a positive normalized solution of T c^(m−1) = λc, allowing any such solution because positive Z-eigenvectors may not be unique.Its defining interaction is multiplicative: the centralities of the other nodes in a hyperedge contribute as a product.Source: §2.2 · p. 5
• A ZEC vector is proportional to a best rank-one approximation vector of the adjacency tensor, but computing such approximations is NP-hard and standard shifted methods may miss unstable ZEC vectors.The paper uses a dynamical-systems method in its computational experiments; it can compute unstable eigenvectors but lacks theoretical convergence guarantees.Source: §2.2 · pp. 6–7

2.3. H-eigenvector centrality (HEC)

• HEC uses a positive normalized H-eigenvector satisfying T c^(m−1) = λc^m; unlike ZEC, its positive eigenvector is unique up to scaling.The paper motivates this formulation on dimensional-analysis grounds and notes that power-method-like algorithms are guaranteed to converge and work well in practice.Source: §2.3 · p. 7

2.4. Analysis of an illustrative example: the sunflower with singleton core

• In singleton-core sunflowers, all three centralities rank the core above other nodes, but ZEC can be nonunique only when m = 3 and ties non-core nodes within each petal.CEC’s core score exceeds other nodes’ scores for finite m and r ≥ 2; the figure states that ZEC ratios do not depend on m and HEC ratios tend to uniform as m grows.Source: §2.4 · pp. 8–9, Figure 1 · p. 8

2.4. Analysis of an illustrative example: the sunflower with singleton core.

• For a sunflower, ZEC has a unique score vector with center-to-other-node ratio √r when m ≠ 3, but infinitely many score vectors when m = 3.In the m = 3 case, non-center nodes can have different scores despite the sunflower’s symmetry, while the center remains highest; the scores are independent of m.Source: §2.4 · p. 9
• For the sunflower, HEC gives a center-to-other-node score ratio of r^(1/m), which approaches 1 as m grows with r fixed.In the same asymptotic analysis, the HEC center score approaches the other nodes’ scores, while the relative CEC and ZEC scores depend only on the number of hyperedges.Source: §2.4 · p. 10, §2.5 · p. 10

2.5. Recap: which centrality should we use?

• CEC uses familiar nonnegative matrix theory but lacks nonlinear structure; HEC is nonlinear and computationally attractive, while ZEC may be non-unique and lacks scalable guaranteed algorithms.CEC and HEC have proper dimensional analysis, unlike ZEC; ZEC can retain the rank-1 approximation interpretation of graph eigenvector centrality.Source: §2.5 · p. 10
• The authors conclude that no centrality is superior in all cases and suggest that multiple centralities can provide features for machine-learning tasks.They report that the three centralities can yield qualitatively different results on real-world data in the next section.Source: §2.5 · p. 10

Experimental setup

• The analysis computes CEC, ZEC, and HEC on the largest connected component of nine hypergraphs constructed from three datasets at uniformities 3, 4, and 5.The n-gram data use frequent word sequences, Ask Ubuntu hyperedges represent tags used together on a question, and DAWN hyperedges represent drug combinations reported by a patient.Source: §3 · pp. 10–12
• ZEC need not be unique; the analysis uses the vector reached most often across 100 runs with random starting points.The authors note that any of the resulting ZEC vectors is a valid centrality.Source: §3 · p. 11

N-grams

• For 5-grams, ZEC ranks “world” 12th and “people” 14th, above their CEC ranks of 64 and 39 and HEC ranks of 84 and 44.CEC and HEC’s top 20 words are nearly all stop words or conjunctions across the n-gram sizes; ZEC has the same pattern for 3- and 4-grams.Source: §3 · p. 11, Table 2 · p. 14
• For n-grams, rank correlations often reach local minima for k between 20 and a few hundred, then rise as larger k includes tail nodes with less ranking difference.The comparisons correlate the ranks of the same top-k nodes under pairs of centrality vectors.Source: §3 · p. 11
• As n-gram hypergraph uniformity increases, centrality rankings become less correlated, and ZEC ranks many top nodes differently from CEC and HEC.For the top few hundred nodes, Figure 2 reports correlations below 0.4 for the 5-uniform hypergraph.Source: §3 · p. 12, Figure 2 · p. 14

Ask Ubuntu

• In Ask Ubuntu’s 4- and 5-uniform hypergraphs, ZEC ranks Windows-related tags relatively higher, while version-number tags rank lower as uniformity increases.For the 5-uniform hypergraph, “windows-8,” “windows,” and “windows-7” rank 8th, 9th, and 10th with ZEC, versus ranks 28th, 22nd, and 26th with CEC and 21st, 18th, and 20th with HEC.Source: §3 · p. 12, Table 3 · p. 15
• For Ask Ubuntu, the centralities are relatively correlated at 3-uniformity, but ZEC is less correlated with CEC and HEC at 4- and 5-uniformity.The top-10 CEC and ZEC subvectors have a rank correlation of 0.05 for the 4-uniform hypergraph.Source: §3 · p. 12, Figure 3 · p. 15

DAWN

• On DAWN, ZEC is negatively or nearly uncorrelated with CEC and HEC at 3-uniformity, while all three are positively correlated at 4- and 5-uniformity.For the 4-uniform hypergraph, rank correlations remain above 0.75 for all measured top-k subvectors.Source: §3 · p. 12, Figure 4 · p. 16

4. Discussion.

• The three centralities are not universally superior to one another, and their eigenvectors can provide qualitatively different results.The authors suggest using multiple centralities to study data rather than treating scores as useful in isolation.Source: §4 · p. 17
• Z- and H-eigenvectors are among the most well-understood and commonly used tensor eigenvectors, though other tensor eigenvectors and Perron-Frobenius theories could support new centralities.The paper distinguishes its tensor-multilinear approach from other hypergraph centralities that do not relate to the multilinear tensor structure studied here.Source: §4 · p. 17
• The centralities remain well-defined for strongly connected hypergraphs with directionality, although computation becomes more challenging.The paper's set-based definition makes its adjacency tensor symmetric; the cited theorems also hold for arbitrary irreducible nonnegative tensors.Source: §4 · p. 17
• The methods rely on symmetric tensor theory and are studied for uniform hypergraphs; the discussion suggests ways to combine or embed different hyperedge sizes.One proposed embedding puts a 3-node hyperedge into an order-4 adjacency tensor by adding nonzeros at indices containing only its three nodes.Source: §4 · p. 17
• Hypergraph construction involves choices such as binary versus weighted adjacency tensors and whether to include hyperedges induced by larger sets.The Ask Ubuntu and DAWN datasets illustrate different choices about including induced hyperedges; the methods also work with weighted hypergraphs.Source: §4 · p. 17
• Choosing the right way to construct a hypergraph from data remains a general research challenge.Hypergraphs can nevertheless serve as a convenient abstraction.Source: §4 · p. 18