Data mining techniques for graph and hypergraph analysis

Li, Peiyan (2025): Data mining techniques for graph and hypergraph analysis. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Graph structures are essential for modeling pairwise relationships in systems ranging from social networks to biological interactions and transportation infrastructure. However, in many real-world scenarios, relationships are often beyond pairwise. For example, social networks generally feature group structures where individuals belong to multiple groups simultaneously. The hypergraph structure has been extensively considered to model such higher-order relationships, wherein hyperedges can connect an arbitrary number of nodes. This thesis focuses on developing scalable and interpretable data mining algorithms for graph and hypergraph analysis, advancing techniques to handle complex relational patterns in these networks. We explore information diffusion in hypergraphs and study the information coverage maximization problem in this scenario. Traditional information diffusion models are designed primarily for ordinary graphs. To address this limitation, we propose HIC, the Hypergraph Independent Cascade model, which extends the conventional independent cascade model to accommodate hypergraphs. Building on HIC, we propose a novel influence maximization problem: the information coverage maximization problem in hypergraphs. Unlike traditional influence maximization, which focuses on identifying influential nodes, we target to identify key groups. We establish the NP-hardness of this problem and demonstrate the submodular monotonicity of the information spread function. To solve the problem efficiently, we developed a heuristic approach called InfDis, inspired by the Degree Discount algorithm. Extensive experiments validate the effectiveness and efficiency of this approach. The second task addressed in the thesis is hyperlink prediction, which involves predicting interactions among multiple entities. While existing solutions generally operate on the entire hypergraph, we propose the first subgraph-based hyperlink prediction approach that captures localized characteristics of central hyperedges while mitigating scalability concerns. The proposed method, SSF, focuses on localized subgraph patterns and extracts interpretable features using structural heuristics such as walks and loops.Additionally, its edge-weakening scheme adapts to varying hypergraph densities, enabling fine-grained feature learning. We conduct extensive experiments to validate SSF's adaptive capacity, evaluate the effectiveness of its feature components, and assess its robustness across various parameter configurations. Next, we focus on a fundamental problem—graph classification. For this problem, we propose RWF, a graph fingerprinting technique that combines structural role-based vertex partitioning with local connection strength measurement. By creating soft alignments of node subsets across graphs of varying sizes, RWF generates topology-aware fingerprints that capture intra- and inter-subset connectivity. Further, RWF supports the integration of node attributes to enhance classification performance. Empirical assessment encompassing a wide range of graph datasets demonstrates that RWF achieves high computational efficiency while maintaining robust classification accuracy. Collectively, this thesis introduces a novel problem formulation and presents three scalable, interpretable techniques designed to address key challenges in graph and hypergraph analysis.

Abstract

Graphstrukturen sind entscheidend für die Modellierung paarweiser Beziehungen in Systemen, die von sozialen Netzwerken über biologische Interaktionen bis hin zu Verkehrsinfrastrukturen reichen. In vielen realen Szenarien gehen Beziehungen jedoch oft über Paare hinaus. So weisen soziale Netzwerke beispielsweise Gruppenstrukturen auf, in denen Individuen gleichzeitig mehreren Gruppen angehören. Die Hypergraph-Struktur wird häufig genutzt, um solche höherstufigen Beziehungen abzubilden, wobei Hyperkanten eine beliebige Anzahl von Knoten verbinden können. Diese Arbeit konzentriert sich auf die Entwicklung skalierbarer und interpretierbarer Data-Mining-Algorithmen zur Analyse von Graphen und Hypergraphen, um Techniken für den Umgang mit komplexen relationalen Mustern in diesen Netzwerken voranzutreiben. Wir untersuchen die Informationsverbreitung in Hypergraphen und adressieren das Problem der Maximierung der Informationsabdeckung. Herkömmliche Diffusionsmodelle sind primär für Standardgraphen konzipiert. Um diese Einschränkung zu überwinden, schlagen wir HIC (Hypergraph Independent Cascade) vor, das das klassische unabhängige Kaskadenmodell auf Hypergraphen erweitert. Basierend auf HIC formulieren wir ein neuartiges Einflussmaximierungsproblem: die Maximierung der Informationsabdeckung in Hypergraphen. Im Gegensatz zur traditionellen Einflussmaximierung, die einflussreiche Knoten identifiziert, zielen wir auf Schlüsselgruppen ab. Wir beweisen die NP-Härte dieses Problems und zeigen die submodulare Monotonie der Informationsausbreitungsfunktion. Zur effizienten Lösung entwickelten wir einen heuristischen Ansatz namens InfDis, inspiriert vom Degree-Discount-Algorithmus. Umfangreiche Experimente bestätigen die Wirksamkeit und Effizienz dieses Ansatzes. Die zweite untersuchte Aufgabe ist die Hyperlink-Vorhersage, die die Prognose von Interaktionen zwischen mehreren Entitäten betrifft. Während bestehende Lösungen üblicherweise den gesamten Hypergraphen analysieren, schlagen wir den ersten teilgraphbasierten Ansatz vor, der lokalisierte Merkmale zentraler Hyperkanten erfasst und gleichzeitig Skalierbarkeitsprobleme mindert. Die Methode SSF konzentriert sich auf lokale Teilgraphmuster und extrahiert interpretierbare Merkmale mittels struktureller Heuristiken wie Pfaden und Schleifen. Ein integriertes Kantenabschwächungsschema passt sich variierenden Hypergraphdichten an und ermöglicht feingranulare Merkmalslernprozesse. Experimente validieren SSFs Adaptionsfähigkeit, die Effektivität seiner Merkmalskomponenten und seine Robustheit unter verschiedenen Parameterkonfigurationen. Im dritten Schwerpunkt behandeln wir die Grundaufgabe der Graphklassifizierung. Hierfür entwickeln wir RWF, eine Graph-Fingerabdrucktechnik, die strukturell rollenbasierte Knotenpartitionierung mit lokalen Verbindungsstärkemessungen kombiniert. Durch weiche Ausrichtungen von Knotenteilmengen über Graphen variierender Größe erzeugt RWF topologiebewusste Fingerabdrücke, die intra- und intersubset-Konnektivität erfassen. Zudem unterstützt RWF die Integration von Knotenattributen zur Steigerung der Klassifizierungsleistung. Empirische Auswertungen über diverse Graphdatensätze zeigen, dass RWF hohe Recheneffizienz bei robusten Klassifizierungsgenauigkeiten erreicht. Zusammenfassend führt diese Arbeit eine neuartige Problemformulierung ein und präsentiert drei skalierbare, interpretierbare Techniken zur Lösung zentraler Herausforderungen in der Graph- und Hypergraphenanalyse.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: Graph Mining, Hypergraph Mining, Data Mining
• Themengebiete: 500 Naturwissenschaften und Mathematik ; 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 26. Juni 2025
• 1. Bericht­erstatter:in: Böhm, Christian