周宝健-大规模图上的高效局部计算与优化.pdf

1、ML-SummitML-SummitML-SummitML-SummitML-SummitML-SummitML-SummitML-SummitML-SummitML-Summit19-04-2025Fudan UniversityZhouBaojianGraphsVery Large Optimization on Efficient Local Computation and 全球机器学习技术大会20251ML-SummitML-SummitSummary&PerspectivesWorksOurAlgorithmsLocalGraphsonLearning录目2ML-SummitML-S

2、ummitVery Large GraphsFacebooks social network with 3 billion usersAmazons product graph featuring 12 million productsGoogles knowledge graph containing 570 million entities and 18 billion factsThese graph datasets help build more effective models(e.g.,when integrated with LLMs),butthey also pose si

3、gnificant challenges to standard graph-learning algorithms.3ML-SummitML-SummitLearning on Very Large Graphs-ClassicsCommunity Detectionh=expt(I P)sRankingf=(I (1 )AD1)1sNode embeddingE=log?m(PT)D1?logb4ML-SummitML-SummitLearning on Very Large Graphs-GNNsGNNs with LLMsAPPNP model iteratesZ(0)=H=f(X),

4、Z(k+1)=(1 )AZ(k)+H,Z(K)=softmax?(1 )AZ(K1)+H?5ML-SummitML-SummitLearning on Very Large Graphs-In-context LearningIn-context learning(ICL)in GPT-3Solving linear system via ICLIn each prompt,it iteratesyi=wxisupp(xi)=Neighbors of node i6ML-SummitML-Summit目录Learning on GraphsLocal AlgorithmsOur WorksSu

5、mmary&Perspectives7ML-SummitML-SummitWhat is a local algorithm?A local algorithm is one that finds a good approximation near a given vertex withoutlooking at the whole graph.In broad terms,given a graph-induced matrix M,approximately solveMx=bwithout directly performing the operation Mx(t).Initially

6、 considered inSublinear time algorithms(Rubinfeld and Shapira,2011)Local computational algorithms(Alon et.al.,2012)So,why local algorithms?Save time by not using the whole graphGive information about specific parts of the graph quickly8ML-SummitML-SummitWhat is a local algorithm?A local algorithm is