AMAtsushi Miyauchi

Atsushi Miyauchi

*This is an algorithmically generated author record based on publicly available information.

Atsushi Miyauchi has a total of 40 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    JECHO: Scalable Echo Chamber Detection via Jaccard-based Homophily and Seed Expansion

    by Ali Safarpoor Dehkordi, Atsushi Miyauchi, Francesco Bonchi, Ahad N. Zehmakan

  • Open Access

    A Survey on Centrality and Importance Measures in Hypergraphs: Categorization and Empirical Insights

    by Jaewan Chun, Fanchen Bu, Yeongho Kim, Atsushi Miyauchi, Francesco Bonchi, Kijung Shin

    Identifying central entities and interactions is a fundamental problem in network science. While well-studied for graphs (pairwise relations), many biological and social systems exhibit higher-order interactions best modeled by hypergraphs. This has led to a proliferation of specialized hypergraph centrality measures, but the field remains fragmented and lacks a unifying framework. This article addresses this gap by providing the first systematic survey of 39 distinct measures. We introduce a novel taxonomy classifying them as (1) structural (topology-based), (2) functional (impact on system dynamics), or (3) contextual (incorporating external features). We also present an experimental assessment comparing their empirical similarity and computation time. Finally, we discuss applications, establishing a coherent roadmap for future research in this area.


  • Open Access

    Q-DISCO: Query-Centric Densest Subgraphs in Networks with Opinion Information

    by Tianyi Chen, Atsushi Miyauchi, Charalampos E. Tsourakakis

    Given a network G=(V,E), where each node v is associated with a vector 𝒩 𝔿 ∈ ℝ d representing its opinion about d different topics, how can we uncover subsets of nodes that not only exhibit exceptionally high density but also possess positively aligned opinions on multiple topics? In this paper we focus on this novel algorithmic question, that is essential in an era where digital social networks are hotbeds of opinion formation and dissemination. We introduce a novel methodology anchored in the well-established densest subgraph problem. We analyze the computational complexity of our formulation, indicating that our problem is NP-hard and eludes practically acceptable approximation guarantees. To navigate these challenges, we design two heuristic algorithms: the first is predicated on the Lagrangian relaxation of our formulation, while the second adopts a peeling algorithm based on the dual of a Linear Programming relaxation. We elucidate the theoretical underpinnings of their performance and validate their utility through empirical evaluation on real-world datasets. Among others, we delve into Twitter datasets we collected concerning timely issues, such as the Ukraine conflict and the discourse surrounding COVID-19 mRNA vaccines, to gauge the effectiveness of our methodology. Our empirical investigations verify that our algorithms are able to extract valuable insights from networks with opinion information.


  • Open Access

    Untapping the Power of Indirect Relationships in Entity Summarization

    by Atefeh Moradan, Mohammad Sorkhpar, Atsushi Miyauchi, Davide Mottin, Ira Assent

    Knowledge graphs form large networks of millions of entities (e.g., Michelle Obama, Barack Obama) and relationships (e.g., married). To obtain an overview of the entity, we need to inspect a potentially large number of relationships to other entities. For this reason, entity summarization aims to extract succinct but expressive descriptions of each entity. Yet, existing methods build their summaries only based on the immediate connections of an entity, disregarding how indirect relationships contain essential information for describing the entity (e.g., understanding Michelle Obama also via her husband's role as former president). We propose IRES, an unsupervised entity summarization method built on graph theoretical principles. We draw a notable connection between the informativeness of a summary and graph partitioning, and devise an effective approach to learn diverse aspects that characterize an entity. In a comprehensive experimental study, IRES shows superior summary quality. In particular, when full neighborhood information is available, IRES outperforms existing methods by 6 percentage points F1 while maintaining competitive computational efficiency.


  • Open Access

    Local Centrality Minimization with Quality Guarantees

    by Atsushi Miyauchi, Lorenzo Severini, Francesco Bonchi

    Centrality measures, quantifying the importance of vertices or edges, play a fundamental role in network analysis. To date, triggered by some positive approximability results, a large body of work has been devoted to studying centrality maximization, where the goal is to maximize the centrality score of a target vertex by manipulating the structure of a given network. On the other hand, due to the lack of such results, only very little attention has been paid to centrality minimization, despite its practical usefulness. In this study, we introduce a novel optimization model for local centrality minimization, where the manipulation is allowed only around the target vertex. We prove the NP-hardness of our model and that the most intuitive greedy algorithm has a quite limited performance in terms of approximation ratio. Then we design two effective approximation algorithms: The first algorithm is a highly-scalable algorithm that has an approximation ratio unachievable by the greedy algorithm, while the second algorithm is a bicriteria approximation algorithm that solves a continuous relaxation based on the Lovász extension, using a projected subgradient method. To the best of our knowledge, ours are the first polynomial-time algorithms with provable approximation guarantees for centrality minimization. Experiments using a variety of real-world networks demonstrate the effectiveness of our proposed algorithms: Our first algorithm is applicable to million-scale graphs and obtains much better solutions than those of scalable baselines, while our second algorithm is rather strong against adversarial instances.


  • Top Cited Papers
    Open Access

    A Survey on the Densest Subgraph Problem and its Variants

    by Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, Francesco Bonchi

    The Densest Subgraph Problem requires us to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.


  • Open Access

    Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity

    by Atsushi Miyauchi, Tianyi Chen, Konstantinos Sotiropoulos, Charalampos E. Tsourakakis

    Dense subgraph discovery methods are routinely used in a variety of applications including the identification of a team of skilled individuals for collaboration from a social network. However, when the network's node set is associated with a sensitive attribute such as race, gender, religion, or political opinion, the lack of diversity can lead to lawsuits. In this work, we focus on the problem of finding a densest diverse subgraph in a graph whose nodes have different attribute values/types that we refer to as colors. We propose two novel formulations motivated by different realistic scenarios. Our first formulation, called the densest diverse subgraph problem (DDSP), guarantees that no color represents more than some fraction of the nodes in the output subgraph, which generalizes the state-of-the-art due to Anagnostopoulos et al. (CIKM 2020). By varying the fraction we can range the diversity constraint and interpolate from a diverse dense subgraph where all colors have to be equally represented to an unconstrained dense subgraph. We design a scalable Ω(1/√n)-approximation algorithm, where n is the number of nodes. Our second formulation is motivated by the setting where any specified color should not be overlooked. We propose the densest at-least-→k-subgraph problem (Dal→kS), a novel generalization of the classic DalkS, where instead of a single value k, we have a vector k of cardinality demands with one coordinate per color class. We design a 1/3-approximation algorithm using linear programming together with an acceleration technique. Computational experiments using synthetic and real-world datasets demonstrate that our proposed algorithms are effective in extracting dense diverse clusters.


  • Open Access

    Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks

    by Yasushi Kawase, Atsushi Miyauchi, Hanna Sumita

    Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, where we have a number of edge sets called layers, which encode different types of connections and/or time-dependent connections over the same set of vertices. Among many network analysis techniques, dense subgraph discovery, aiming to find a dense component in a network, is an essential primitive with a variety of applications in diverse domains. In this paper, we introduce a novel optimization model for dense subgraph discovery in multilayer networks. Our model aims to find a stochastic solution, i.e., a probability distribution over the family of vertex subsets, rather than a single vertex subset, whereas it can also be used for obtaining a single vertex subset. For our model, we design an LP-based polynomial-time exact algorithm. Moreover, to handle large-scale networks, we also devise a simple, scalable preprocessing algorithm, which often reduces the size of the input networks significantly and results in a substantial speed-up. Computational experiments demonstrate the validity of our model and the effectiveness of our algorithms.


  • Open Access

    対応に苦慮したニボルマブによる気管軟骨炎の1例

    by Hiroaki Ito, Masahiro Komori, Atsushi Miyauchi, Shu-Ichi Matsumoto, Masamitsu Hyodo

    免疫チェックポイント阻害薬投与後にまれな免疫関連有害事象である気管軟骨炎を発症し,治療に苦慮した症例を経験した。症例は66歳の男性,主訴は発熱,咳嗽,喀痰,全身倦怠感であった。右梨状陥凹癌に対する放射線化学療法と手術の後にリンパ節再発を認めた。救済治療としてニボルマブを54週,23クール投与後に本症を発症した。CRP上昇と気管気管支壁肥厚による内腔狭窄を認めた。高用量ステロイド治療にて一旦は改善したが,ステロイドを漸減すると再燃し,メトトレキサートを併用しても病勢は沈静化しなかった。マトリックスメタロプロテナーゼ3が上昇してきたためトシリズマブ,コルヒチンを追加し,寛解を得ることができた。