Graphs have rich structures at both local and global scales. By exploiting structural properties in certain graph problems, it is possible to design computationally efficient algorithms or refine performance analysis. This thesis is divided into two parts: (i) designing new methods for discovering structure from graphs and (ii) studying the interplay between graphs and combinatorial multi-arm bandits. They differ in how structures are defined, discovered, and utilized. In part (i), we start with a graph-mining problem on signed networks [TOG20], where the graph patterns we aim to detect are groups with mostly positive intragroup edges and mostly negative inter-group edges. We design our objective such that, given a solution, it reflects how well that solution matches the desired pattern. Our proposed algorithm makes no assumptions about the graph. It demonstrates competitive empirical performance in real-world graphs and synthetic graphs. The performance evaluation is conducted through a worst-case analysis, approximating the optimal solution. Moreover, we extend our conflicting group detection [BGG+19, TOG20] as well as other graph-mining tasks (such as fair densest-subgraph detection [ABF+20], two-community detection [New06]) to a memory-limited and pass-limited setting. Under such a setting, Randomized SVD, which has been proposed by [HMT11], is the most preferable method in the memory-limited and pass-limited setting. However, for an input matrix of size n °ø n, it has no guarantee in the o(ln n)-pass regime, which is of most interest to practitioners. We hence derive a tighter analysis [TWA+22] for Randomized SVD for positive semi-definite matrices in any number of passes and for indefinite matrices under certain conditions. Furthermore, we initiate the study of a mixture of Johnson-Lindenstrauss distribution and the 0/1 Bernoulli distribution. We show that this mixture helps make the detection of 2-conflicting groups [BGG+19]

more efficient. In part (ii), we study combinatorial multi-arm bandits problems, where the graph properties play important roles but are somewhat hidden in the optimization problem. Instead, one derives the fundamental limit bounds on either the expected sample complexity or the expected cumulative regret, typically in the informationtheoretical sense, and then explores the abstract properties associated with those bounds to solve the problem satisfactorily, either statistically or computationally.

We focus on combiantorial semi-bandits where the learner observes individual feedbacks for each arm part of the selection. This formulation models many real-world problems, including online ranking [DKC21] in recommendation systems, network routing [CLK+14] in internet service providers, loan assignment [KWA+14], path planning [JMKK21], and influence marketing [Per22]. For best arm identification with fixed confidence, we propose the first polynomial-time algorithm whose sample complexity is instance-specifically optimal in high confidence regime and has polynomial dependency on the number of arms in moderate confidence regime. For regret minimization, we propose the first algorithm whose per-round time complexity is sublinear in the number of arms while matching the instance-specifically gap-dependent lower bound asymptotically.

Grafer har rika strukturer både på lokal och global skala. Genom att utnyttja strukturella egenskaper i vissa grafproblem är det möjligt att designa beräkningsmässigt effektiva algoritmer eller förfina prestandaanalysen. Denna avhandling är uppdelad i två delar: (i) att designa nya metoder för att upptäcka struktur från grafer och (ii) att studera samspelet mellan grafer och kombinatoriska multi-armbanditer. De skiljer sig .t i hur strukturer definieras, upptäcks och utnyttjas.

I del (i) börjar vi med ett grafgruvningsproblem på signerade nätverk [TOG20], där de grafmönster vi siktar på att upptäcka är grupper med mestadels positiva intra-gruppkanter och mestadels negativa inter-gruppkanter. Vi utformar vårt mål så att, givet en lösning, det återspeglar hur väl den lösningen matchar det önskade mönstret. Vår föreslagna algoritm ger inga antaganden om grafen. Den visar konkurrenskraftig empirisk prestanda i verkliga grafer och syntetiska grafer. Prestandautvärderingen genomförs genom en värsta fall-analys, som approximativt finner den optimala lösningen. Dessutom utvidgar vi vår konfliktgruppsdetektion [BGG+19, TOG20] samt andra grafgruvningsuppgifter (såsom rättvis tätaste subgrafdetektion [ABF+20], två-samhällesdetektion [New06]) till en minnesbegränsad och passbegränsad inställning. Under en sådan inställning är Randomized SVD, som föreslagits av [HMT11], den mest föredragna metoden i en minnesbegränsad och passbegränsad inställning. Men för en ingångsmatris av storlek n × n har den ingen garanti i o(ln n)-passregimen, vilket är av största intresse för praktiker. Vi härleder därför en stramare analys [TWA+22] för Randomized SVD för positivt semi-definita matriser i vilket antal pass som helst och för indefinita matriser under vissa villkor. Vidare initierar vi studien av en blandning av Johnson-Lindenstrauss distribution och 0/1 Bernoulli-distributionen. Vi visar att denna blandning hjälper till att göra detektionen av 2-konfliktgrupper [BGG+19] mer effektiv.

I del (ii) studerar vi kombinatoriska multi-arm banditproblem, där grafer- nas egenskaper spelar viktiga roller men är något dolda i optimeringsproblemet. I stället härleder man de fundamentala gränserna för antingen den förväntade provtagningskomplexiteten eller den förväntade kumulativa ånger, vanligtvis i informations-teoretisk mening, och utforskar sedan de abstrakta egenskaperna associerade med dessa gränser för att lösa problemet på ett tillfredsställande sätt, antingen statistiskt eller beräkningsmässigt. Vi fokuserar på kombinatoriska semi-banditer där läraren observerar individuella återkopplingar för varje arm som är en del av urvalet. Denna formulering modellerar många verkliga problem, inklusive online ranking [ DKC21 ] i rekommendationssystem, nätverksrouting [ CLK+14] hos internetleverantörer, lånefördelning [ KWA+14 ], vägplanering [JMKK21 ], och influencer-marknadsföring [ Per22 ]. För bästa armidentifiering med fast förtroende föreslår vi den första polynomtidalgoritmen vars provtagningskomplexitet är instansspecifikt optimal i hög förtroenderegim och har polynomberoende på antalet armar i måttlig förtroenderegim. För ångerminimering föreslår vi den första algoritmen vars per-rundans tidskomplexitet är sublinjär i antalet armar samtidigt som den matchar den instansspecifikt gapberoende nedre gränsen asymptotiskt.